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 bi 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 bi, where bi 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^5 
1<= bi <= 10^8
1 <= Q <= 10^5
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).
intMax = 10**8+1
def treeQuery(tree1, tree2, start, end, rangeStart, rangeEnd, index):
    if rangeStart<=start and rangeEnd>=end:
        return tree1[index], tree2[index]
    if end<rangeStart or start>rangeEnd:
        return intMax, -1
    middleIndex = (start + end) / 2
    a,c = treeQuery(tree1, tree2, start, middleIndex, rangeStart, rangeEnd, (2*index)+1)
    b,d = treeQuery(tree1, tree2, middleIndex+1, end, rangeStart, rangeEnd, (2*index)+2)
    return min(a,b), max(c,d)
 
def treeMaxQuery(tree, start, end, rangeStart, rangeEnd, index):
    if rangeStart<=start and rangeEnd>=end:
        return -1
    if end<rangeStart or start>rangeEnd:
        return tree[index]
    middleIndex = (start + end) / 2
    return max(treeMaxQuery(tree, start, middleIndex, rangeStart, rangeEnd, (2*index)+1),
               treeMaxQuery(tree, middleIndex+1, end, rangeStart, rangeEnd, (2*index)+2))
 
def makeTree(nums, start, end, tree1, tree2, index):
    if start==end:
        tree1[index] = nums[start]
        tree2[index] = nums[start]
        return nums[start], nums[start]
    middleindex = (start + end) / 2
    a,c = makeTree(nums, start, middleindex, tree1, tree2, (index*2)+1)
    b,d = makeTree(nums, middleindex+1, end, tree1, tree2, (index*2)+2)
    tree1[index] = min(a,b)
    tree2[index] = max(c,d)
    return tree1[index], tree2[index]
 
def getSegmentationTree(nums,n):
    import math
    val = (2*(2**int(math.ceil(math.log(n,2))))) - 1
    tree1 = [0] * val
    tree2 = [0] * val
    start = 0
    end = n-1
    startindex = 0
    makeTree(nums, start, end, tree1, tree2, startindex)
    return tree1, tree2
 
def main():
    import sys
    tokenizedInput = map(int, sys.stdin.read().split())    # Read at once, tokenize
    n = tokenizedInput[0]
    nums = tokenizedInput[1:n+1]
    tree1, tree2 = getSegmentationTree(nums,n)
    q = tokenizedInput[n+1]
    readAt = n+2
    s = ""
    for i in xrange(q):
        num1,num2 = tokenizedInput[readAt:readAt+2]
        minR, maxR = treeQuery(tree1, tree2, 0, n-1, num1, num2,0)
        ans = float(maxR-minR)/2
        if maxR!=tree2[0]:
            max1 = tree2[0]
        else:
            max1 = treeMaxQuery(tree2,0,n-1, num1, num2,0)
        maax = max(max1, ans)
        maax += minR
        s += "%.1f\n" % maax
        readAt+=2
    print s[:-1]
 
main()