Uzb Eng

C8A. BAMBLBI
: 2 c
: 64

Deseptikonlar bilan olishuvdan keyin Bamblbini nimasidir sinib qoldi. Hozir u tushunarsiz ishlar qilmoqda. Hozir u qandaydir qiziqarli masalani ishlamoqchi. Masala shartlarni keltiramiz: Musbat natural sonlarda aniqlangan ikkita funksiya kiritamiz.
Birinchi funksiya MEX(a1, a2, , an) funksiyasi bolib, u a1, a2, , an sonlar ichida mavjud bolmagan eng kichik natural sonni aniqlaydi.
Ikkinchi funksiya esa GCD(a1, a2, , an) funksiyasi bolib, u a1, a2, , an sonlarning EKUB ini aniqlaydi. Bamblbi natural sonlar toplamini hosil qildi va hozir quyidagilarni bajara oladi.
Ixtiyoriy L va R sonlari uchun aL dan aR gacha bolgan kesmada barcha qism toplamlarni olamiz va ularning MEX() funksiyalarini hisoblaymiz. Songra aniqlangan barcha MEX() funksiya qiymatlari (aytish lozimki ularning soni 2R - L + 1 1 ta boladi) uchun EKUBni hisoblaymiz .
Bamblbining hisoblash tezligi bunga imkon bermaydi. Unga yordam bering.

:
Birinchi satrda n (1 ≤ n ≤ 104) Bamblbi tomonidan hosil qilingan massiv uzunligi berilgan.
Ikkinchi satrda probel bilan ajratilgan holda massiv elementlari ai (1 ≤ ai ≤ 109) berilgan.
Uchinchi satrda q (1 ≤ q ≤ 104) sorovlar soni berilgan.
Keyingi har bir q satrda ikkita L va R (1 ≤ L ≤R ≤ n) hisoblanishi kerak bolgan kesma berilgan

:
q ta satrda i-sorovga javoblarni chiqaring.

1
1
1
1 1
4
1 2 3 4
2
1 1
1 4
2
1 2
3
1 1
2 2
1 2
2




2
1



2
1
1
: Arifmetika
: acm.tuit.uz 8-contest


Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.