#include<stdio.h>
#include<math.h>
#define MAX 1000000
#define MAX_MIN 10000 // > sqrt(MAX)
#define INF 10000000
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
int minarr[MAX_MIN];
int maxarr[MAX_MIN];
int findmin(int arr[],int st,int en){
int i;
int small=arr[st];
for(i=st+1;i<en;i++){
if(small>arr[i])
small=arr[i];
}
return small;
}
int calmin(int a[],int n,int root){
int m=0,i;
for(i=0;i<n;i+=root) {
if(n>i+root)
minarr[m++]=findmin(a,i,i+root);
else
minarr[m++]=findmin(a,i,n);
}
return m;
}
int calmax(int a[],int n,int root){
int m=0,i;
for(i=0;i<n;i+=root) {
if(n>i+root)
maxarr[m++]=findmin(a,i,i+root);
else
maxarr[m++]=findmin(a,i,n);
}
return m;
}
int querymin(int L, int R,int root,int a[])
{
int i;
if(L > R)
return INF;
int lblock = L/root, rblock = R/root;
int val = INF;
if(lblock == rblock)
for(i = L; i <= R; i++)
val = min(val, a[i]);
else
{
for(i = L; i < (lblock+1)*root; i++)
val = min(val, a[i]);
for(i = lblock+1; i < rblock; i++)
val = min(val, minarr[i]);
for(i = rblock*root; i <= R; i++)
val = min(val, a[i]);
}
return val;
}
int querymax(int L, int R,int root,int a[])
{
int i;
if(L > R)
return INF;
int lblock = L/root, rblock = R/root;
int val = INF;
if(lblock == rblock)
for(i = L; i <= R; i++)
val = min(val, a[i]);
else
{
for(i = L; i < (lblock+1)*root; i++)
val = min(val, a[i]);
for(i = lblock+1; i < rblock; i++)
val = min(val, maxarr[i]);
for(i = rblock*root; i <= R; i++)
val = min(val, a[i]);
}
return val;
}
int main(){
int i,m,n,root,q;
int beg,end;
int maxq[MAX],minq[MAX];
int t,t1,t2,t3,t4;
double ans;
for(i=0;i<n;i++) {
maxq[i]=(-1*minq[i]);
}
calmin(minq,n,root);
calmax(maxq,n,root);
for(i=0;i<q;i++) {
scanf("%d %d",&beg
,&end
); t=querymin(beg,end,root,minq);
t1=-1*querymax(beg,end,root,maxq);
t2=-1*querymax(0,beg-1,root,maxq);
t3=-1*querymax(end+1,n-1,root,maxq);
t4=max(t2,t3);
ans = max( (t1-t)/2.0,t4*1.0);
ans=ans+t/1.0;
printf("%.1lf\n", ans
+ 0.01); }
return 0;
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8bWF0aC5oPgojZGVmaW5lIE1BWCAxMDAwMDAwCiNkZWZpbmUgTUFYX01JTiAxMDAwMCAvLyA+IHNxcnQoTUFYKSAKI2RlZmluZSBJTkYgMTAwMDAwMDAKI2RlZmluZSBtaW4oYSxiKSBhPGI/YTpiCiNkZWZpbmUgbWF4KGEsYikgYT5iP2E6YgoKaW50IG1pbmFycltNQVhfTUlOXTsKaW50IG1heGFycltNQVhfTUlOXTsKCmludCBmaW5kbWluKGludCBhcnJbXSxpbnQgc3QsaW50IGVuKXsKaW50IGk7CmludCBzbWFsbD1hcnJbc3RdOwpmb3IoaT1zdCsxO2k8ZW47aSsrKXsKICBpZihzbWFsbD5hcnJbaV0pCiAgICBzbWFsbD1hcnJbaV07Cn0KcmV0dXJuIHNtYWxsOwp9CgppbnQgY2FsbWluKGludCBhW10saW50IG4saW50IHJvb3QpewppbnQgbT0wLGk7CmZvcihpPTA7aTxuO2krPXJvb3QpIHsKICAgaWYobj5pK3Jvb3QpCiAgICBtaW5hcnJbbSsrXT1maW5kbWluKGEsaSxpK3Jvb3QpOwogICBlbHNlCiAgICBtaW5hcnJbbSsrXT1maW5kbWluKGEsaSxuKTsKfQpyZXR1cm4gbTsKfQoKaW50IGNhbG1heChpbnQgYVtdLGludCBuLGludCByb290KXsKIGludCBtPTAsaTsKIGZvcihpPTA7aTxuO2krPXJvb3QpIHsKICAgaWYobj5pK3Jvb3QpCiAgICBtYXhhcnJbbSsrXT1maW5kbWluKGEsaSxpK3Jvb3QpOwogICBlbHNlCiAgICBtYXhhcnJbbSsrXT1maW5kbWluKGEsaSxuKTsKfQogcmV0dXJuIG07Cn0KCmludCBxdWVyeW1pbihpbnQgTCwgaW50IFIsaW50IHJvb3QsaW50IGFbXSkKewogIGludCBpOwogIGlmKEwgPiBSKQogICByZXR1cm4gSU5GOwogIGludCBsYmxvY2sgPSBML3Jvb3QsIHJibG9jayA9IFIvcm9vdDsKICBpbnQgdmFsID0gSU5GOwogIGlmKGxibG9jayA9PSByYmxvY2spCiAgIGZvcihpID0gTDsgaSA8PSBSOyBpKyspCiAgICB2YWwgPSBtaW4odmFsLCBhW2ldKTsKICBlbHNlCiAgewogICBmb3IoaSA9IEw7IGkgPCAobGJsb2NrKzEpKnJvb3Q7IGkrKykKICAgIHZhbCA9IG1pbih2YWwsIGFbaV0pOwogICBmb3IoaSA9IGxibG9jaysxOyBpIDwgcmJsb2NrOyBpKyspCiAgICB2YWwgPSBtaW4odmFsLCBtaW5hcnJbaV0pOwogICBmb3IoaSA9IHJibG9jaypyb290OyBpIDw9IFI7IGkrKykKICAgIHZhbCA9IG1pbih2YWwsIGFbaV0pOwogIH0KIHJldHVybiB2YWw7Cn0KCmludCBxdWVyeW1heChpbnQgTCwgaW50IFIsaW50IHJvb3QsaW50IGFbXSkKewogIGludCBpOwogIGlmKEwgPiBSKQogICByZXR1cm4gSU5GOwogIGludCBsYmxvY2sgPSBML3Jvb3QsIHJibG9jayA9IFIvcm9vdDsKICBpbnQgdmFsID0gSU5GOwogIGlmKGxibG9jayA9PSByYmxvY2spCiAgIGZvcihpID0gTDsgaSA8PSBSOyBpKyspCiAgICB2YWwgPSBtaW4odmFsLCBhW2ldKTsKICBlbHNlCiAgewogICBmb3IoaSA9IEw7IGkgPCAobGJsb2NrKzEpKnJvb3Q7IGkrKykKICAgIHZhbCA9IG1pbih2YWwsIGFbaV0pOwogICBmb3IoaSA9IGxibG9jaysxOyBpIDwgcmJsb2NrOyBpKyspCiAgICB2YWwgPSBtaW4odmFsLCBtYXhhcnJbaV0pOwogICBmb3IoaSA9IHJibG9jaypyb290OyBpIDw9IFI7IGkrKykKICAgIHZhbCA9IG1pbih2YWwsIGFbaV0pOwogIH0KIHJldHVybiB2YWw7Cn0KCmludCBtYWluKCl7CiBpbnQgaSxtLG4scm9vdCxxOwogaW50IGJlZyxlbmQ7CmludCBtYXhxW01BWF0sbWlucVtNQVhdOwogaW50IHQsdDEsdDIsdDMsdDQ7CiBkb3VibGUgYW5zOwogc2NhbmYoIiVkIiwmbik7CiByb290PShpbnQpc3FydChuKTsKIGZvcihpPTA7aTxuO2krKykgewogICAgc2NhbmYoIiVkIiwmbWlucVtpXSk7CiAgICBtYXhxW2ldPSgtMSptaW5xW2ldKTsKIH0KIGNhbG1pbihtaW5xLG4scm9vdCk7CiBjYWxtYXgobWF4cSxuLHJvb3QpOwogc2NhbmYoIiVkIiwmcSk7CiBmb3IoaT0wO2k8cTtpKyspIHsKICBzY2FuZigiJWQgJWQiLCZiZWcsJmVuZCk7CiAgICAgICAgdD1xdWVyeW1pbihiZWcsZW5kLHJvb3QsbWlucSk7CiAgICAgICAgdDE9LTEqcXVlcnltYXgoYmVnLGVuZCxyb290LG1heHEpOwogICAgICAgIHQyPS0xKnF1ZXJ5bWF4KDAsYmVnLTEscm9vdCxtYXhxKTsKICAgICAgICB0Mz0tMSpxdWVyeW1heChlbmQrMSxuLTEscm9vdCxtYXhxKTsKICAgICAgICB0ND1tYXgodDIsdDMpOwogICAgICAgIGFucyA9IG1heCggKHQxLXQpLzIuMCx0NCoxLjApOwogICAgICAgICAgICBhbnM9YW5zK3QvMS4wOwogICAgICAgICAgICBwcmludGYoIiUuMWxmXG4iLCBhbnMgKyAwLjAxKTsKICAgICB9CiAgICAgcmV0dXJuIDA7CiAgIH0=