Вам дано масив цілих невід'ємних чисел довжини n і m запитів. Кожен запит — два числа l та r. Для кожного запиту знайдіть максимум по попарних найбільших спільних дільниках підмасиву від l до r, тобто:
Перший рядок містить одне ціле число n (2≤n≤2⋅105) — розмір масиву.
Другий рядок містить n цілих чисел a1,a2,…,an (1≤ai≤106) — елементи масиву.
Третій рядок містить одне ціле число m (1≤m≤2⋅105) — кількість запитів.
i-ий з наступних m рядків містить два цілі числа li, ri (1≤li<ri≤n) — межі запиту.
Для кожного запиту виведіть одне ціле число — відповідь на нього.
gcd(a,b) — найбільший спільний дільник чисел a,b.
Розглянемо другий приклад:
У перших чотирьох запитах відрізок складається лише з двох чисел, отже відповідь — їхній найбільший спільний дільник.
Запит (1,5): найбільший спільний дільник має числа a1 та a4, gcd(a1,a4)=gcd(10,50)=10.
Запит (3,5): потрібно порахувати max(gcd(a3,a4),gcd(a3,a5),gcd(a4,a5))=max(2,3,1)=3.
Запит (1,3): потрібно порахувати max(gcd(a1,a2),gcd(a1,a3),gcd(a2,a3))=max(1,2,3)=3.
(12 балів): m,n,ai≤200;
(7 балів): m,n≤200;
(17 балів): ai≤50;
(7 балів): всі ai — степені двійок;
(27 балів): m,n≤15000;
(13 балів): m,n≤35000;
(17 балів): без додаткових обмежень.