//
// mstick.cpp
//
//
// Created by Gaurav Gulzar on 22/01/14.
//
//
#include <iostream>
using namespace std;
#include <cmath>
#include <cstdio>
double *a;
int *mn,*mx, n;
//int a[] = {2,4,3,1,6,7,8,9,1,7};
//int mn[32],mx[32];
void initialize(int node, int b, int e){
if(b==e) {
mx[node] = b;
mn[node] = b;
return;
}
initialize(2*node, b, (b+e)/2);
initialize(2*node+1,(b+e)/2 + 1, e);
mn[node] = ((a[mn[2*node]] <= a[mn[2*node+1]]) ? mn[2*node] : mn[2*node+1]);
mx[node] = (a[mx[2*node]] >= a[mx[2*node+1]]) ? mx[2*node] : mx[2*node+1];
}
int query_min(int node, int b, int e, int i, int j){
if(i>e || j<b)
return -1;
if(i<=b && j>=e)
return mn[node];
int p1 = query_min(2*node,b,(b+e)/2,i,j);
int p2 = query_min(2*node+1,(b+e)/2+1,e,i,j);
if(p1==-1)
return mn[node] = p2;
if(p2==-1)
return mn[node] = p1;
if(a[p1]<=a[p2])
return mn[node] = p1;
return mn[node] = p2;
}
int query_max(int node, int b, int e, int i, int j){
if(i>e || j<b)
return -1;
if(i<=b && j>=e)
return mx[node];
int p1 = query_max(2*node,b,(b+e)/2,i,j);
int p2 = query_max(2*node+1,(b+e)/2+1,e,i,j);
if(p1 == -1)
return mx[node] = p2;
if(p2 == -1)
return mx[node] = p1;
if(a[p1]>=a[p2])
return mx[node] = p1;
return mx[node] = p2;
}
int main() {
/*int a[] = {2,4,3,1,6,7,8,9,1,7};
//int n = sizeof(a)/sizeof(a[0]);
//int m[32];
for(int i=0; i<32; i++)
mn[i] = -1;
for(int i=0; i<32; i++)
mx[i] = -1;
initialize(1,0,9);
for(int i=0; i<32; i++)
cout << mn[i] << " ";
cout << "\n";
cout << query_min(1,0,9,2,6) << " "<< query_max(1,0,9,2,6)<<"\n";*/
cin >> n;
double t[n];
for(int i=0; i<n; i++)
scanf("%lf",&t[i]);
int q;
cin >> q;
int l,r;
a = t;
//for(int i=0; i<n; i++)
// printf("%.1f ",a[i]);
int s = (int)(log10(n)/log10(2));
s = 2*( int)(pow(2.0f,(s+1)));
int t2[s],t3[s];
for(int i=0;i<s;i++)
t2[i] = t3[i] = -1;
mn = t2;
mx = t3;
initialize(1,0,n-1);
for(int i=0; i<q; i++){
scanf("%d %d",&l,&r);
int v1 = query_min(1,0,n-1,l,r) ;
int v2 = query_max(1,0,n-1,l,r);
//cout << v1 <<v2<< "\n";
int vr1 = query_max(1,0,n-1,0,l-1);
int vr2 = query_max(1,0,n-1,r+1,n-1);
double m = (a[vr1] >= a[vr2]?a[vr1]:a[vr2]);
m = ((m+a[v1] >= a[v1]+(a[v2]-a[v1])/2.0)? m+a[v1] : a[v1]+(a[v2]-a[v1])/2.0);
printf("%.1lf\n",m);
}
return 0;
}
Ly8KLy8gIG1zdGljay5jcHAKLy8gIAovLwovLyAgQ3JlYXRlZCBieSBHYXVyYXYgR3VsemFyIG9uIDIyLzAxLzE0LgovLwovLwoKI2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxjc3RkaW8+CmRvdWJsZSAqYTsKaW50ICptbiwqbXgsIG47Ci8vaW50IGFbXSA9IHsyLDQsMywxLDYsNyw4LDksMSw3fTsKLy9pbnQgbW5bMzJdLG14WzMyXTsKdm9pZCBpbml0aWFsaXplKGludCBub2RlLCBpbnQgYiwgaW50IGUpewogICAgaWYoYj09ZSkgewogICAgICAgIG14W25vZGVdID0gYjsKICAgICAgICBtbltub2RlXSA9IGI7CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgaW5pdGlhbGl6ZSgyKm5vZGUsIGIsIChiK2UpLzIpOwogICAgaW5pdGlhbGl6ZSgyKm5vZGUrMSwoYitlKS8yICsgMSwgZSk7CiAgICBtbltub2RlXSA9ICgoYVttblsyKm5vZGVdXSA8PSBhW21uWzIqbm9kZSsxXV0pID8gbW5bMipub2RlXSA6IG1uWzIqbm9kZSsxXSk7CiAgICBteFtub2RlXSA9IChhW214WzIqbm9kZV1dID49IGFbbXhbMipub2RlKzFdXSkgPyBteFsyKm5vZGVdIDogbXhbMipub2RlKzFdOwp9CgppbnQgcXVlcnlfbWluKGludCBub2RlLCBpbnQgYiwgaW50IGUsIGludCBpLCBpbnQgail7CiAgICBpZihpPmUgfHwgajxiKQogICAgICAgIHJldHVybiAtMTsKICAgIAogICAgaWYoaTw9YiAmJiBqPj1lKQogICAgICAgIHJldHVybiBtbltub2RlXTsKICAgIAogICAgaW50IHAxID0gcXVlcnlfbWluKDIqbm9kZSxiLChiK2UpLzIsaSxqKTsKICAgIGludCBwMiA9IHF1ZXJ5X21pbigyKm5vZGUrMSwoYitlKS8yKzEsZSxpLGopOwogICAgCiAgICBpZihwMT09LTEpCiAgICAgICAgcmV0dXJuIG1uW25vZGVdID0gcDI7CiAgICBpZihwMj09LTEpCiAgICAgICAgcmV0dXJuIG1uW25vZGVdID0gcDE7CiAgICBpZihhW3AxXTw9YVtwMl0pCiAgICAgICAgcmV0dXJuIG1uW25vZGVdID0gcDE7CiAgICByZXR1cm4gbW5bbm9kZV0gPSBwMjsKfQoKaW50IHF1ZXJ5X21heChpbnQgbm9kZSwgaW50IGIsIGludCBlLCBpbnQgaSwgaW50IGopewogICAgaWYoaT5lIHx8IGo8YikKICAgICAgICByZXR1cm4gLTE7CiAgICAKICAgIGlmKGk8PWIgJiYgaj49ZSkKICAgICAgICByZXR1cm4gbXhbbm9kZV07CiAgICBpbnQgcDEgPSBxdWVyeV9tYXgoMipub2RlLGIsKGIrZSkvMixpLGopOwogICAgaW50IHAyID0gcXVlcnlfbWF4KDIqbm9kZSsxLChiK2UpLzIrMSxlLGksaik7CiAgICAKICAgIGlmKHAxID09IC0xKQogICAgICAgIHJldHVybiBteFtub2RlXSA9IHAyOwogICAgaWYocDIgPT0gLTEpCiAgICAgICAgcmV0dXJuIG14W25vZGVdID0gcDE7CiAgICBpZihhW3AxXT49YVtwMl0pCiAgICAgICAgcmV0dXJuIG14W25vZGVdID0gcDE7CiAgICByZXR1cm4gbXhbbm9kZV0gPSBwMjsKfQoKaW50IG1haW4oKSB7CiAgICAvKmludCBhW10gPSB7Miw0LDMsMSw2LDcsOCw5LDEsN307CiAgICAvL2ludCBuID0gc2l6ZW9mKGEpL3NpemVvZihhWzBdKTsKICAgIC8vaW50IG1bMzJdOwogICAgZm9yKGludCBpPTA7IGk8MzI7IGkrKykKICAgICAgICBtbltpXSA9IC0xOwogICAgZm9yKGludCBpPTA7IGk8MzI7IGkrKykKICAgICAgICBteFtpXSA9IC0xOwogICAgCiAgICBpbml0aWFsaXplKDEsMCw5KTsKICAgIGZvcihpbnQgaT0wOyBpPDMyOyBpKyspCiAgICAgICAgY291dCA8PCBtbltpXSA8PCAiICI7CiAgICBjb3V0IDw8ICJcbiI7CiAgICBjb3V0IDw8IHF1ZXJ5X21pbigxLDAsOSwyLDYpIDw8ICIgIjw8IHF1ZXJ5X21heCgxLDAsOSwyLDYpPDwiXG4iOyovCiAgICBjaW4gPj4gbjsKICAgIGRvdWJsZSB0W25dOwogICAgZm9yKGludCBpPTA7IGk8bjsgaSsrKQogICAgICAgIHNjYW5mKCIlbGYiLCZ0W2ldKTsKICAgIAogICAgaW50IHE7CiAgICBjaW4gPj4gcTsKICAgIGludCBsLHI7CiAgICBhID0gdDsKICAgIC8vZm9yKGludCBpPTA7IGk8bjsgaSsrKQogICAgICAvLyAgcHJpbnRmKCIlLjFmICIsYVtpXSk7CiAgICAKICAgIGludCBzID0gKGludCkobG9nMTAobikvbG9nMTAoMikpOwogICAgcyA9IDIqKCBpbnQpKHBvdygyLjBmLChzKzEpKSk7CiAgICBpbnQgdDJbc10sdDNbc107CiAgICBmb3IoaW50IGk9MDtpPHM7aSsrKQogICAgICAgIHQyW2ldID0gdDNbaV0gPSAtMTsKICAgIG1uID0gdDI7CiAgICBteCA9IHQzOwogICAgaW5pdGlhbGl6ZSgxLDAsbi0xKTsKICAgIGZvcihpbnQgaT0wOyBpPHE7IGkrKyl7CiAgICAgICAgc2NhbmYoIiVkICVkIiwmbCwmcik7CiAgICAgICAgaW50IHYxID0gcXVlcnlfbWluKDEsMCxuLTEsbCxyKSA7CiAgICAgICAgaW50IHYyID0gcXVlcnlfbWF4KDEsMCxuLTEsbCxyKTsKICAgICAgICAvL2NvdXQgPDwgdjEgPDx2Mjw8ICJcbiI7CiAgICAKICAgICAgICBpbnQgdnIxID0gcXVlcnlfbWF4KDEsMCxuLTEsMCxsLTEpOwogICAgICAgIGludCB2cjIgPSBxdWVyeV9tYXgoMSwwLG4tMSxyKzEsbi0xKTsKICAgICAgICBkb3VibGUgbSA9IChhW3ZyMV0gPj0gYVt2cjJdP2FbdnIxXTphW3ZyMl0pOwogICAgICAgIG0gPSAoKG0rYVt2MV0gPj0gYVt2MV0rKGFbdjJdLWFbdjFdKS8yLjApPyBtK2FbdjFdIDogYVt2MV0rKGFbdjJdLWFbdjFdKS8yLjApOwogICAgICAgIHByaW50ZigiJS4xbGZcbiIsbSk7CiAgICB9CiAgICByZXR1cm4gMDsKfQo=