Masala #ZOGKDO6LGL
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.
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.
# | 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 |