Рус 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 bo’lib, u a1, a2, …, an sonlar ichida mavjud bo’lmagan eng kichik natural sonni aniqlaydi.
Ikkinchi funksiya esa GCD(a1, a2, …, an) funksiyasi bo’lib, u a1, a2, …, an sonlarning EKUB ini aniqlaydi. Bamblbi natural sonlar to’plamini hosil qildi va hozir quyidagilarni bajara oladi.
Ixtiyoriy L va R sonlari uchun aL dan aR gacha bo’lgan kesmada barcha qism to’plamlarni olamiz va ularning MEX() funksiyalarini hisoblaymiz. So’ngra aniqlangan barcha MEX() funksiya qiymatlari (aytish lozimki ularning soni 2R - L + 1 – 1 ta bo’ladi) 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) – so’rovlar soni berilgan.
Keyingi har bir q satrda ikkita L va R (1 ≤ L ≤R ≤ n) – hisoblanishi kerak bo’lgan kesma berilgan

Выходные данные:
q ta satrda i-so’rovga 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.