НСД sorğuları

Verilmiş massiv tam qeyri-mənfi ədədlərdən ibarətdir və uzunluğu $n$-dir. Həmçinin, $m$ sorğu mövcuddur. Hər bir sorğu iki ədəd $l$ və $r$-dən ibarətdir. Hər bir sorğu üçün $l$-dən $r$-ə qədər olan altmassivin cüt-cüt ən böyük ortaq bölənlərinin maksimumunu tapın, yəni:

Giriş verilənləri

Birinci sətir bir tam ədəd $n$ ($2\le n\le 2\cdot 10^5$) — massiv ölçüsünü göstərir.

İkinci sətir $n$ tam ədəd $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^6$) — massiv elementlərini göstərir.

Üçüncü sətir bir tam ədəd $m$ ($1\le m\le 2\cdot 10^5$) — sorğuların sayını göstərir.

Növbəti $m$ sətirin hər biri iki tam ədəd $l_i$, $r_i$ ($1\le l_i<r_i\le n$) — sorğunun sərhədlərini göstərir.

Çıxış verilənləri

Hər bir sorğu üçün bir tam ədəd çıxış edin — həmin sorğunun cavabı.

Nümunələr

Qeyd

$\gcd (a,b)$  — ədədlərin $a,b$ ən böyük ortaq bölənidir.

İkinci nümunəni nəzərdən keçirək:

• İlk dörd sorğuda seqment yalnız iki ədəddən ibarətdir, buna görə cavab onların ən böyük ortaq bölənidir.

• Sorğu $(1,5)$: ən böyük ortaq bölən $a_1$ və $a_4$ ədədlərindədir, $\gcd (a_1,a_4)=\gcd (10,50)=10$.

• Sorğu $(3,5)$: $\max (\gcd (a_3,a_4),\gcd (a_3,a_5),\gcd (a_4,a_5))=\max (2,3,1)=3$ hesablanmalıdır.

• Sorğu $(1,3)$: $\max (\gcd (a_1,a_2),\gcd (a_1,a_3),\gcd (a_2,a_3))=\max (1,2,3)=3$ hesablanmalıdır.

Qiymətləndirmə

1. ($12$ bal): $m,n,a_i\le 200$;

2. ($7$ bal): $m,n\le 200$;

3. ($17$ bal): $a_i\le 50$;

4. ($7$ bal): bütün $a_i$ — iki qüvvətləri;

5. ($27$ bal): $m,n\le 15000$;

6. ($13$ bal): $m,n\le 35000$;

7. ($17$ bal): əlavə məhdudiyyətlərsiz.