Задачи
НСД запити
НСД запити
Вам дано масив цілих невід'ємних чисел довжини $n$ і $m$ запитів. Кожен запит~--- два числа $l$ та $r$. Для кожного запиту знайдіть максимум по попарних найбільших спільних дільниках підмасиву від $l$ до $r$, тобто: $$\smash{\displaystyle\max_{l \leq i < j \leq r}} \gcd(a_i, a_j)$$
\InputFile
Перший рядок містить одне ціле число $n$ ($2 \le n \le 2 \cdot 10^5 $)~--- розмір масиву.
Другий рядок містить $n$ цілих чисел $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^6$)~--- елементи масиву.
Третій рядок містить одне ціле число $m$ ($1 \le m \le 2 \cdot 10^5 $)~--- кількість запитів.
$i$-ий з наступних $m$ рядків містить два цілі числа $l_i$, $r_i$ ($1 \le l_i < r_i \le n$)~--- межі запиту.
\OutputFile
Для кожного запиту виведіть одне ціле число~--- відповідь на нього.
\Note
$\gcd(a, b)$ ~--- найбільший спільний дільник чисел $a, b$.
Розглянемо другий приклад:
\begin{itemize}
\item У перших чотирьох запитах відрізок складається лише з двох чисел, отже відповідь~--- їхній найбільший спільний дільник.
\item Запит $(1, 5)$: найбільший спільний дільник має числа $a_1$ та $a_4$, $\gcd(a_1, a_4)=\gcd(10, 50)=10$.
\item Запит $(3, 5)$: потрібно порахувати $\max(\gcd(a_3, a_4), \gcd(a_3, a_5), \gcd(a_4, a_5))=\max(2, 3, 1) = 3$.
\item Запит $(1, 3)$: потрібно порахувати $\max(\gcd(a_1, a_2), \gcd(a_1, a_3), \gcd(a_2, a_3))=\max(1, 2, 3) = 3$.
\end{itemize}
\Scoring
\begin{enumerate}
\item ($12$ балів): $m, n, a_i \leq 200$;
\item ($7$ балів): $m, n \leq 200$;
\item ($17$ балів): $a_i \leq 50$;
\item ($7$ балів): всі $a_i$~--- степені двійок;
\item ($27$ балів): $m, n \leq 15000$;
\item ($13$ балів): $m, n \leq 35000$;
\item ($17$ балів): без додаткових обмежень.
\end{enumerate}
Входные данные #1
3 2 3 6 3 1 2 2 3 1 3
Выходные данные #1
1 3 3
Входные данные #2
5 10 3 6 50 9 7 1 2 2 3 3 4 4 5 1 5 3 5 1 3
Выходные данные #2
1 3 2 1 10 3 3