P3889 [GDOI2014] Eating

Thanks to @FFjet for the reminder, the 8th test point is corrupted and has been temporarily removed.

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.

- 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 $M$ lines. The $i$-th line contains the maximum possible joy value $D$ for the $i$-th selection time.

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