Masala #ZOGKDO6LGL

Xotira 256 MB Vaqt 5000 ms
14

Tug'ilgan kun sovg'asi va so'rovlar

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.


Kiruvchi ma'lumotlar:

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\)


Chiquvchi ma'lumotlar:

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


Misollar
# input.txt output.txt
1
5 1
1 2 1 1 1
1 3
1
2
5 2
1 1 1 1 1
2 4
2 3
0
1