33007번 - Greatest of the Greatest Common Divisors 다국어

You are given a sequence of integers and a number of intervals in the sequence. The intervals are specified by their leftmost and rightmost positions. An interval consisting of $k$ integers has $k(k - 1)/2$ pairs of integers at different positions, which have their greatest common divisors. For each given interval, find the greatest one among such greatest common divisors.

For example, when the sequence is $(a_1, \dots , a_6) = (10, 20, 30, 40, 50, 60)$, and the whole sequence is specified as the interval, the following $15$ pairs of two integers at different positions $x$ and $y$, and their greatest common divisors should be considered.

The greatest of the greatest common divisors of the $15$ pairs is $\gcd(30, 60) = 30$, in this case.

The input consists of a single test case of the following format.

$n$

$a_1$ $\cdots$ $a_n$

$q$

$l_1$ $r_1$

$\vdots$

$l_q$ $r_q$

The first line contains an integer n, which is the number of integers in the given sequence, satisfying $2 ≤ n ≤ 10^5$. The second line contains $n$ positive integers $a_1$ through $a_n$ specifying the sequence. None of them exceeds $10^5$.

The third line contains a positive integer $q$, specifying the number of intervals in the sequence to be considered, which does not exceed $10^5$. It is followed by $q$ lines, each specifying an interval in the sequence to be considered. The $i$-th line of them has two integers, $l_i$ and $r_i$ ($1 ≤ l_i < r_i ≤ n$), specifying the interval $a_{l_i}$ through $a_{r_i}$ in the sequence.

Output $q$ lines, the $i$-th line of which should have the greatest of the greatest common divisors of all pairs in the interval specified by $l_i$ and $r_i$.