Problem Description

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

Just when W Senior Brother was still excited, a piece of bad news came: Foodie L Senior Sister actually found out about this and is on her way here. W Senior Brother's heart instantly sank, but the clever W Senior Brother also immediately thought of a strategy to deal with L Senior Sister...

Now, L Senior Sister has arrived at the sushi restaurant. She first looked around at the scenery and found that there was only one customer, herself. Below is L Senior Sister's dining instructions:

1. The sushi in the restaurant is arranged in a row across N plates, numbered from left to right as 1 to N.

2. The number of sushi on each plate is fixed and protected by glass.

3. At intervals, there will be a dining time. L Senior Sister can choose one plate within a continuous interval [l, r] and another plate outside this interval (if there are plates outside the interval).

L Senior Sister found that the chefs in this sushi restaurant are very fast, always able to restore the sushi quantities to their original state before the next dining time.

As a dignified and discerning foodie, L Senior Sister also has her own rules. After choosing two plates of sushi, she will decide to eat exactly D pieces of sushi per mouthful, ensuring that the two plates of sushi can be eaten completely without any leftovers. For example, if the quantities of the two plates are 2 and 4, then D=1 or D=2 can both completely eat the two plates clean. If the quantities are 3 and 5, then only D=1 will work.

As a discerning foodie, L Senior Sister doesn't care about the quantity of sushi she eats; what she cares about is the feeling of eating multiple pieces of sushi in one mouthful. Therefore, if L Senior Sister can eat D pieces of sushi in one mouthful, her pleasure value is D. However, if she fails to choose two plates of sushi, her pleasure value is 0.

Now, L Senior Sister knows the quantity of sushi on each plate. She wants to know the maximum pleasure value she can obtain after each dining time.

Input Format

The first line contains an integer N, representing the number of sushi plates.

The second line contains N integers a1, a2, ..., aN, where ai represents the quantity of sushi on the i-th plate.

The third line contains an integer M, representing the number of dining times.

The next M lines each contain two integers li, ri (1 <= li <= ri <= N), with the meanings as described in the problem statement.

Output Format

Output M lines, where the i-th line represents the maximum pleasure value D that Senior Sister can achieve during the i-th dining time.

Sample Input and Output

Input Sample #1

5
1 2 3 4 5
2
2 3
2 4

Output Sample #1

2
1

Input Sample #2

5
2 4 8 16 32
2
3 4
2 3

Output Sample #2

16
8

Notes

Sample Explanation

In Sample 1, during the first dining time, L Senior Sister can choose plates 2 and 4, allowing her to eat 2 pieces of sushi at a time, ensuring both plates are eaten clean. During the second dining time, no matter which two plates she chooses, she can only eat 1 piece at a time.

In Sample 2, during the first dining time, L Senior Sister can choose plates with 16 and 32 pieces. During the second dining time, she can choose plates with 8 and 16 pieces, or 8 and 32 pieces.

For 20% of the data, N <= 100, M <= 100, max(a1, a2, ..., aN) <= 100.

For 50% of the data, N <= 10000, M <= 10000, max(a1, a2, ..., aN) <= 10000.

For 100% of the data, N <= 100000, M <= 100000, max(a1, a2, ..., aN) <= 100000.

见题面 Input 部分

见题面 Output 部分