Description

Senior Brother W had planned for a long time and finally succeeded in opening a sushi restaurant in BG.

Just as he was still excited, bad news came: foodie Senior Sister L actually learned about this and was on her way. Senior Brother W instantly felt a chill, but being clever, he immediately came up with a strategy to deal with Senior Sister L.

When Senior Sister L arrived at the sushi restaurant, she first looked around and found that she was the only customer. Below are her selection rules:

1. The sushi in the restaurant is arranged in a single row of $N$ plates, numbered from $1$ to $N$ from left to right.
2. The number of sushi on each plate is fixed and protected by a glass cover.
3. At each selection time, Senior Sister L may choose one plate from a continuous interval $[l, r]$, and then choose another plate outside that interval (if there are plates outside the interval).

Senior Sister L finds that the chefs here work very fast and can always restore the sushi counts to their original numbers before the next selection time.

As a foodie with standards, after selecting two plates, Senior Sister L will decide to eat exactly $D$ pieces of sushi per bite, such that both plates can be finished exactly with no leftovers. For example, if the two plates contain $2$ and $4$ pieces, then $D = 1$ or $D = 2$ will finish both plates exactly. If the two plates contain $3$ and $5$ pieces, then only $D = 1$ works.

Senior Sister L does not care about the total amount of food; she cares about the feeling of eating multiple pieces in one bite. Thus, if she can eat $D$ pieces per bite, her joy value is $D$. If she cannot select two plates, her joy value is $0$.

Given the number of sushi on each plate, Senior Sister L wants to know, after each selection time, what is the maximum joy value she can obtain.

Input Format

• The first line contains an integer $N$, the number of sushi plates.
• The second line contains $N$ integers $a_1, a_2, \dots, a_N$, where $a_i$ is the number of sushi on the $i$-th plate.
• The third line contains an integer $M$, the number of selection times.
• The next $M$ lines each contain two integers $l_i, r_i$ with $1 \le l_i \le r_i \le N$, as described above.

Output Format

Output $M$ lines. The $i$-th line contains the maximum possible joy value $D$ for the $i$-th selection time.

5
1 2 3 4 5
2
2 3
2 4

2
1

5
2 4 8 16 32
2
3 4
2 3

16
8

Hint

Sample explanation:

• In sample 1, for the first selection time, you can choose $2$ and $4$, so Senior Sister L can eat $2$ pieces per bite and finish both plates exactly. For the second selection time, no matter which two plates she chooses, she can only eat $1$ piece per bite.
• In sample 2, for the first selection time, she can choose $16$ and $32$. For the second selection time, she can choose $8$ and $16$ or $8$ and $32$.

Constraints:

• For 20% of the testdata, $N \le 100$, $M \le 100$, $\max(a_1, a_2, \dots, a_N) \le 100$.
• For 50% of the testdata, $N \le 10000$, $M \le 10000$, $\max(a_1, a_2, \dots, a_N) \le 10000$.
• For 100% of the testdata, $N \le 100000$, $M \le 100000$, $\max(a_1, a_2, \dots, a_N) \le 100000$.

Translated by ChatGPT 5