Masala #M099C

Bugun Mirzohidning bugun tug‘ilgan kuni, va uning yaqin do‘sti Jamshid unga maxsus sovg‘a tayyorlagan. Jamshid Mirzohidga katta qiziqarli topshiriq berdi: N ta tabiiy sonlardan iborat massiv va Q ta savol. U shunday dedi:

"Mirzohid, agar sen ushbu savollarga to‘g‘ri javob bersang, tug‘ilgan kuning uchun tayyorlagan sovg‘amni olasan! Savollar oddiy: har bir savolda men bir intervalni ko‘rsataman, va sen shu intervalda aynan ikki marta uchraydigan turli sonlarning sonini topishing kerak."

Jamshid kulib qo‘shib qo‘ydi: "Bu unchalik qiyin emas, ammo sovg‘ani olmoqchi bo‘lsang, savollarning hammasini hal qilishing kerak!"

Mirzohidning qiziqishi oshdi va u topshiriqni bajarishga kirishdi. Endi u Jamshidning barcha savollariga javob berib, sovg‘ani qo‘lga kiritishi kerak. Bu ish juda ko'p vaqt olishi mumkin va u bayramni nishonlashi kerak. Shu sababli bu vazifani sizga topshirdi.

Kirish faylining birinchi satrida \(N\) va \(Q\) - massiv uzunligi va so'rovlar soni kiritiladi.

Keyingi satrda \(N\) da butun son - \(A\) massiv elementlari kiritiladi.

Keyingi \(Q\) ta satrning har birida ikkitadan butun son \(L_i\) va \(R_i\) kiritiladi.

\(1 \le N, Q \le 5 \times 10^5\)

\(1 \le A_i \le 10^9\)

\(1 \le L_i \le R_i \le N\)

Har bir so'rov uchun yangi satrda shu oraliqdagi aynan ikki marta uchragan elementlar sonini chop eting.