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).

-------------------------------------------------------editorial-------------------------------------------------------------------------------------

PROBLEM

You are given N matchsticks arranged in a straight line, with their rear ends touching each other. You are also given the rate of burn for every matchstick (possibly same) in number of seconds it takes to burn it out. If a matchstick is lit from both ends, it burns out twice as fast - taking half as much time.

Answer several queries of the following type efficiently

All the matchsticks in the range L to R, inclusive are lit from their front ends simultaneously. Find how much time it takes for all the matchsticks to burn out.

QUICK EXPLANATION

For each query, the operation performed plays out in the following way

• All the matchsticks in the range L to R are lit from their front ends.
• The matchstick that burns quickest in the range L to R burns out and ignites all the other matchsticks on theirrear ends.
• The matchticks in the range L to R now burn out twice as fast.
• All the other matchsticks burn out at their original rate.

We can find the time taken in all the steps above using only the following pieces of information for the segment L toR

• Quickest rate of burning for a match in the range L to R.
• Slowest rate of burning for all matches in the range L to R.
• Slowest rate of burning for all matches outside the range L to R.

EXPLANATION

For a given range L to R

• Let m denote the minimum time taken by some matchstick in the range L to R to burn out
• Let M denote the largest time taken by some matchstick in the range L to R to burn out
• Let M' denote the largest time taken by some matchstick outside the range L to R to burn out

The time taken by each of the steps in the scenario described above is as follows

• The matchstick that burns quickest, burns out
  • Takes time m
• The following things happen in parallel
  • The matchsticks in the range L to R now burn out twice as fast
    • Takes time (M - m) / 2
  • The matchsticks outside the range
    • Takes time M'

Thus, the time taken for all the matches to burn out completely is

m + max( (M-m)/2 , M' )

It remains to find efficiently the minimum time some matchstick will take in a range, and the maximum time some matchstick will take in a range.

Such queries can be answered in O(N log N) time by using segment trees. Refer to this topcoder tutorial for a wonderful writeup with code samples on how to get about writing a segment tree. The topcoder tutorial also describes a O(N sqrt(N)) approach as well which will also work within the time limits for this problem.

Two segment trees must be constructed. One to answer queries of the type "minimum in a range", that returns the time it takes for the fastest burning matchstick to burn out. Another to answer queries of the type "maximum in a range" to find M and M' as defined above. Note that M' will itself be the maxmimum of two ranges, 1 to L-1 and R+1 to N respectively.

A lot of solutions were stuck in the caveat that it is required to always print the answer in a single decimal place. Note how the answer will either be integer, or contain a single decimal digit (5). In case the answer is integer, it is required to print a trailing decimal followed by 0.

------------------------------------------------------CODE------------------------------------------------------

#include<iostream>

using namespace std;

#define ren -1111111111

#define rep 1111111111

#include<bits/stdc++.h>

typedef long long int lli;

int qs,qe;

  lli maxi[1000000],mini[1000000],arr[1000000];

 void build(int index,int start,int end)

  {

  // cout<<" building "<<start<<" "<<end<<endl;

  if(start>end) return ;

    if(start==end)

     {

      mini[index]=arr[start];

      maxi[index]=arr[start];

      return ;

     }

     build(2*index,start,(start+end)/2);

      build(2*index+1,(start+end)/2+1,end);

      mini[index]=min(mini[2*index+1],mini[2*index]);

      maxi[index]=max(maxi[2*index+1],maxi[2*index]);

  //return ;

  }

  

   

    lli query(int index ,int start,int end,int type )

     {

       //cout<<"finding start "<<start<<" end "<<end<<" index "<<index<<endl;

         //cout<<" qs "<<qs<<" qe "<<qe<<endl;

       //if(index==0) exit(0);

        if((start>end|| start>qe|| end<qs) && type==1) return ren;

         if((start>end || start>qe || end<qs) && type==0)  return rep;

        else if(start>=qs && end<=qe )

         {

          if(type==1)

          {

          return maxi[index];

          }

          else return mini[index];

         }

         

        lli a=query(2*index,start,(start+end)/2,type);

        lli b=query(2*index+1,(start+end)/2+1,end,type);

        if(type==1) return max(a,b);

        else return min(a,b);

     }

int main()

 {

  int n;

   cin>>n;

    for(int i=0;i<n;i++)

     {

      cin>>arr[i];

     }

      build(1,0,n-1);

       /* cout<<" max tree "<<endl;

         for(int i=1;i<=3;i++) cout<<maxi[i]<<" ";

          cout<<endl;

          cout<<" min tree "<<endl;

         for(int i=0;i<5;i++) cout<<mini[i]<<" ";

          cout<<endl;*/

        

      int q;

       cin>>q;

       while(q--)

        {

       

         cin>>qs>>qe;

          //qs-=1;

          //qe-=1;

          lli vs=qs;

          lli ve=qe;

          

           lli rmin=query(1,0,n-1,0);

           lli rmax=query(1,0,n-1,1);

           

        //      cout<<" range max is "<<rmax<<" r min is "<<rmin<<endl;

            qs=0;

            qe=vs-1;

             

            lli lmax=0,lmin=0;

            

            if(qe<0 || qs>qe) lmax=0;

            

            else

            lmax=query(1,0,n-1,1);

            

            qs=ve+1;

            qe=n-1;

            

             if(qs<=n-1 && qe>=0 && qs<=qe)

             lmin=query(1,0,n-1,1);

             else lmin=0;

             

             

             

             double ans=(double)rmin+max(max((double)(rmax-rmin)/2.0,(double)lmax),(double)lmin);

              printf("%.1lf\n",ans);

        }

 }