#include<bits/stdc++.h>
using namespace std;
long long a[100001];
long long mn[10000000];
long long mx[10000000];
float maxi(float a,float b,float c)
{
if(a>b)
{
return a>c?a:c;
}
else
return b>c?b:c;
}
void buildtreemn(int node,int l,int r)
{
if(l==r){
mn[node]=a[l];
return; }
buildtreemn(node*2,l,(l+r)/2);
buildtreemn(node*2+1,(l+r)/2+1,r);
if(mn[node*2]<mn[node*2+1])
mn[node]=mn[node*2];
else
mn[node]=mn[node*2+1];
}
void buildtreemx(int node,int l,int r)
{
if(l==r){
mx[node]=a[l];
return; }
buildtreemx(node*2,l,(l+r)/2);
buildtreemx(node*2+1,(l+r)/2+1,r);
if(mx[node*2]>mx[node*2+1])
mx[node]=mx[node*2];
else
mx[node]=mx[node*2+1];
}
int querymn(int node,int l,int r,int i,int j)
{
int p1,p2;
if(i>r || j<l)
return -1;
if(l>=i && r<=j)
return mn[node];
p1=querymn(node*2,l,(l+r)/2,i,j);
p2=querymn(node*2+1,(l+r)/2+1,r,i,j);
if (p1 == -1)
return p2;
if (p2 == -1)
return p1;
if (p1 <= p2)
return p1;
else
return p2;
}
int querymx(int node,int l,int r,int i,int j)
{
int p1,p2;
if(i>r || j<l)
return -1;
if(l>=i && r<=j)
return mx[node];
p1=querymx(node*2,l,(l+r)/2,i,j);
p2=querymx(node*2+1,(l+r)/2+1,r,i,j);
if (p1 == -1)
return p2;
if (p2 == -1)
return p1;
if (p1 >= p2)
return p1;
else
return p2;
}
int main()
{
int n,i,j,q;
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
cin>>q;
float ans=0;
buildtreemn(1,0,n-1);
buildtreemx(1,0,n-1);
while(q--)
{
int l,r;
cin>>l>>r;
/*if(n==1)
{
cout<<a[0]<<".0\n";
continue;
}*/
int min1=querymn(1,0,n-1,l,r);
float max1=querymx(1,0,n-1,0,l-1);
float max2=querymx(1,0,n-1,l,r);
float max3=querymx(1,0,n-1,r+1,n-1);
max2=min1+(max2-min1)/2;
max1+=min1;
max3+=min1;
ans=maxi(max1,max2,max3);
if((ans-floor(ans))!=0)
cout<<ans<<"\n";
else
cout<<ans<<".0\n";
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKbG9uZyBsb25nIGFbMTAwMDAxXTsKbG9uZyBsb25nIG1uWzEwMDAwMDAwXTsKbG9uZyBsb25nIG14WzEwMDAwMDAwXTsKZmxvYXQgbWF4aShmbG9hdCBhLGZsb2F0IGIsZmxvYXQgYykKewogICAgaWYoYT5iKQogICAgewogICAgICAgIHJldHVybiBhPmM/YTpjOwogICAgfQogICAgZWxzZQogICAgICAgIHJldHVybiBiPmM/YjpjOwp9CnZvaWQgYnVpbGR0cmVlbW4oaW50IG5vZGUsaW50IGwsaW50IHIpCnsKICAgIGlmKGw9PXIpewogICAgICAgIG1uW25vZGVdPWFbbF07CiAgICAgICAgcmV0dXJuOyB9CiAgICBidWlsZHRyZWVtbihub2RlKjIsbCwobCtyKS8yKTsKICAgIGJ1aWxkdHJlZW1uKG5vZGUqMisxLChsK3IpLzIrMSxyKTsKICAgIGlmKG1uW25vZGUqMl08bW5bbm9kZSoyKzFdKQogICAgICAgIG1uW25vZGVdPW1uW25vZGUqMl07CiAgICBlbHNlCiAgICAgICAgbW5bbm9kZV09bW5bbm9kZSoyKzFdOwp9CnZvaWQgYnVpbGR0cmVlbXgoaW50IG5vZGUsaW50IGwsaW50IHIpCnsKICAgIGlmKGw9PXIpewogICAgICAgIG14W25vZGVdPWFbbF07CiAgICAgICAgcmV0dXJuOyB9CiAgICBidWlsZHRyZWVteChub2RlKjIsbCwobCtyKS8yKTsKICAgIGJ1aWxkdHJlZW14KG5vZGUqMisxLChsK3IpLzIrMSxyKTsKICAgIGlmKG14W25vZGUqMl0+bXhbbm9kZSoyKzFdKQogICAgICAgIG14W25vZGVdPW14W25vZGUqMl07CiAgICBlbHNlCiAgICAgICAgbXhbbm9kZV09bXhbbm9kZSoyKzFdOwp9CmludCBxdWVyeW1uKGludCBub2RlLGludCBsLGludCByLGludCBpLGludCBqKQp7CiAgICBpbnQgcDEscDI7CiAgICBpZihpPnIgfHwgajxsKQogICAgICAgIHJldHVybiAtMTsKICAgIGlmKGw+PWkgJiYgcjw9aikKICAgICAgICByZXR1cm4gbW5bbm9kZV07CiAgICBwMT1xdWVyeW1uKG5vZGUqMixsLChsK3IpLzIsaSxqKTsKICAgIHAyPXF1ZXJ5bW4obm9kZSoyKzEsKGwrcikvMisxLHIsaSxqKTsKICAgIGlmIChwMSA9PSAtMSkKICAgICAgICAgIHJldHVybiBwMjsKICAgICAgaWYgKHAyID09IC0xKQogICAgICAgICAgcmV0dXJuIHAxOwogICAgICBpZiAocDEgPD0gcDIpCiAgICAgICAgICByZXR1cm4gIHAxOwogICAgICBlbHNlCiAgICAgICAgICByZXR1cm4gIHAyOwp9CmludCBxdWVyeW14KGludCBub2RlLGludCBsLGludCByLGludCBpLGludCBqKQp7CiAgICBpbnQgcDEscDI7CiAgICBpZihpPnIgfHwgajxsKQogICAgICAgIHJldHVybiAtMTsKICAgIGlmKGw+PWkgJiYgcjw9aikKICAgICAgICByZXR1cm4gbXhbbm9kZV07CiAgICBwMT1xdWVyeW14KG5vZGUqMixsLChsK3IpLzIsaSxqKTsKICAgIHAyPXF1ZXJ5bXgobm9kZSoyKzEsKGwrcikvMisxLHIsaSxqKTsKICAgIGlmIChwMSA9PSAtMSkKICAgICAgICAgIHJldHVybiBwMjsKICAgICAgaWYgKHAyID09IC0xKQogICAgICAgICAgcmV0dXJuIHAxOwogICAgICBpZiAocDEgPj0gcDIpCiAgICAgICAgICByZXR1cm4gIHAxOwogICAgICBlbHNlCiAgICAgICAgICByZXR1cm4gIHAyOwp9CmludCBtYWluKCkKewogICAgaW50IG4saSxqLHE7CiAgICBjaW4+Pm47CgogICAgZm9yKGk9MDtpPG47aSsrKQogICAgICAgIGNpbj4+YVtpXTsKICAgIGNpbj4+cTsKICAgIGZsb2F0IGFucz0wOwogICAgYnVpbGR0cmVlbW4oMSwwLG4tMSk7CiAgICBidWlsZHRyZWVteCgxLDAsbi0xKTsKICAgIHdoaWxlKHEtLSkKICAgIHsKICAgICAgICBpbnQgbCxyOwogICAgICAgIGNpbj4+bD4+cjsKICAgICAgICAvKmlmKG49PTEpCiAgICAgICAgewogICAgICAgICAgICBjb3V0PDxhWzBdPDwiLjBcbiI7CiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIH0qLwogICAgICAgIGludCBtaW4xPXF1ZXJ5bW4oMSwwLG4tMSxsLHIpOwogICAgICAgIGZsb2F0IG1heDE9cXVlcnlteCgxLDAsbi0xLDAsbC0xKTsKICAgICAgICBmbG9hdCBtYXgyPXF1ZXJ5bXgoMSwwLG4tMSxsLHIpOwogICAgICAgIGZsb2F0IG1heDM9cXVlcnlteCgxLDAsbi0xLHIrMSxuLTEpOwogICAgICAgIG1heDI9bWluMSsobWF4Mi1taW4xKS8yOwogICAgICAgIG1heDErPW1pbjE7CiAgICAgICAgbWF4Mys9bWluMTsKICAgICAgICBhbnM9bWF4aShtYXgxLG1heDIsbWF4Myk7CiAgICAgICAgaWYoKGFucy1mbG9vcihhbnMpKSE9MCkKICAgICAgICBjb3V0PDxhbnM8PCJcbiI7CiAgICAgICAgZWxzZQogICAgICAgIGNvdXQ8PGFuczw8Ii4wXG4iOwogICAgfQogICAgcmV0dXJuIDA7Cn0K