Matchsticks

All submissions for this problem are available.

Chef Ceil has some matchsticks in his kitchen.

Detail of matchsticks:

There are N matchsticks in total. They are numbered from to 0 to N-1 inclusive. All matchsticks have same length. But they may have different rates of burning. For i^th matchstick, we denote b_i as the time required for that matchstick to completely burn-down if lighted at one end. The matchsticks have uniform rate of burning.
If lighted at both ends simultaneously, the matchstick will take only half of the original time to burn down.

Arrangement:

He ties rear end of the all the matchsticks together at one point and the front end is kept free. The matchstick numbered i is adjacent to matchstick numbered i+1 for all 0<= i <=N-2.
Bodies of matchsticks do not touch each other, except at rear end. All matchsticks are kept on the floor.

Task:

There are Q queries, in each query we ask:
If he lights the free end of all matchsticks numbered between L and R both inclusive, what will be the time needed for all matchsticks to get completely burnt.

Input

First line of input contains one integer N, total number of matchsticks. The next line contains N space separated integers b_i, where b_i is the time required for i^th matchstick to completely burn-down if lighted at one end.
Next line contains one integer Q, total number of queries you need to answer. Then there are Q queries in next Q lines. Each line has two space separated integers L and R.

Output

Print Q lines, one for each query, printing the answer for each query, that is, the time it will take for all the matchsticks to get completely burn down. Every time you must print your answer with 1 decimal place.

Constraints:

1 <= N <= 10⁵

1<= b_i <= 10⁸

1 <= Q <= 10⁵

0 <= L <= R <= N-1

Example

Input
1
5
1
0 0
Output
5.0

Input
2
3 5
1
0 1
Output
4.0

Input
18
3 4 2 1 5 7 9 7 10 5 12 3 1 1 2 1 3 2
1
4 10
Output
9.0

Explanation



For the last input, in figure yellow colored matches are lighted by a lighter simultaneously.
The numbers indicate the time required to burn that matchstick (if lighted at one end)
Now the first lighted matchstick will completely burn in 5 seconds. Then it will light up all the rest matches from the rear end.
Some matches will have fire at both ends and thus after 5 seconds, they will start burning with twice the original rate.
Thus time taken for matches to burn completely will be :
(from left to right): 8.0, 9.0, 7.0, 6.0, 5.0, 6.0, 7.0, 6.0, 7.5, 5.0, 8.5, 8.0, 6.0, 6.0, 7.0, 6.0, 8.0, 7.0.
So, the answer will be 9.0 (the maximum among these).