#include <stdio.h>
#include <stdlib.h>
#define left(a) ((a*2)+1)
#define right(a) ((a*2)+2)
#define leftsegment(start,end) start,(start+end)/2
#define rightsegment(start,end) ((start+end)/2)+1,end
/*
Use static arrays instead of pointers
*/
int min[100000];
int max[100000];
int A[100000];
void initialize(int node,int start,int end)
{
if(start==end)
{
min[node]=A[start];
max[node]=A[start];
return;
}
initialize(left(node),leftsegment(start,end));
initialize(right(node),rightsegment(start,end));
if(min[left(node)]<=min[right(node)])
{
min[node]=min[left(node)];
}
else
{
min[node]=min[right(node)];
}
if(max[left(node)]>=max[right(node)])
{
max[node]=max[left(node)];
}
else
{
max[node]=max[right(node)];
}
}
int minquery(int node,int start,int end,int qstart,int qend)
{
int minleft,minright;
if(qstart>end || qend<start)
{
return -1;
}
if(start>=qstart && end<=qend)
{
return min[node];
}
minleft=minquery(left(node),leftsegment(start,end),qstart,qend);
minright=minquery(right(node),rightsegment(start,end),qstart,qend);
if(minleft==-1)
{
return minright;
}
if(minright==-1)
{
return minleft;
}
if(minleft<=minright)
{
return minleft;
}
return minright;
}
int maxquery(int node,int start,int end,int qstart,int qend)
{
int maxleft,maxright;
if(qstart>end || qend<start)
{
return -1;
}
if(start>=qstart && end<=qend)
{
return max[node];
}
maxleft=maxquery(left(node),leftsegment(start,end),qstart,qend);
maxright=maxquery(right(node),rightsegment(start,end),qstart,qend);
if(maxleft==-1)
{
return maxright;
}
if(maxright==-1)
{
return maxleft;
}
if(maxleft>=maxright)
{
return maxleft;
}
return maxright;
}
int main(int argc, char **argv)
{
int N,Q,i,min1,max1,max2,max3,l,r;
double t1,t2,t3,ans;
for(i=0;i<N;i++)
{
}
initialize(0,0,N-1);
for(scanf("%d",&Q
);Q
>0;Q
--) {
min1=minquery(0,0,N-1,l,r);
max1=maxquery(0,0,N-1,l,r);
max1-=min1;
max2=maxquery(0,0,N-1,0,l-1);
max3=maxquery(0,0,N-1,r+1,N-1);
ans=min1;
t1=max1/2.0;
t2=max2;
t3=max3;
if(t2<t3)t2=t3;
if(t1<t2)t1=t2;
ans+=t1;
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KIAojZGVmaW5lIGxlZnQoYSkgKChhKjIpKzEpCiNkZWZpbmUgcmlnaHQoYSkgKChhKjIpKzIpCiAKI2RlZmluZSBsZWZ0c2VnbWVudChzdGFydCxlbmQpIHN0YXJ0LChzdGFydCtlbmQpLzIKI2RlZmluZSByaWdodHNlZ21lbnQoc3RhcnQsZW5kKSAoKHN0YXJ0K2VuZCkvMikrMSxlbmQKCi8qCglVc2Ugc3RhdGljIGFycmF5cyBpbnN0ZWFkIG9mIHBvaW50ZXJzCiovCmludCBtaW5bMTAwMDAwXTsKaW50IG1heFsxMDAwMDBdOwppbnQgQVsxMDAwMDBdOwogCnZvaWQgaW5pdGlhbGl6ZShpbnQgbm9kZSxpbnQgc3RhcnQsaW50IGVuZCkKewoJaWYoc3RhcnQ9PWVuZCkKCXsKCQltaW5bbm9kZV09QVtzdGFydF07CgkJbWF4W25vZGVdPUFbc3RhcnRdOwoJCXJldHVybjsKCX0KIAoJaW5pdGlhbGl6ZShsZWZ0KG5vZGUpLGxlZnRzZWdtZW50KHN0YXJ0LGVuZCkpOwoJaW5pdGlhbGl6ZShyaWdodChub2RlKSxyaWdodHNlZ21lbnQoc3RhcnQsZW5kKSk7CiAKCWlmKG1pbltsZWZ0KG5vZGUpXTw9bWluW3JpZ2h0KG5vZGUpXSkKCXsKCQltaW5bbm9kZV09bWluW2xlZnQobm9kZSldOwoJfQoJZWxzZQoJewoJCW1pbltub2RlXT1taW5bcmlnaHQobm9kZSldOwoJfQogCglpZihtYXhbbGVmdChub2RlKV0+PW1heFtyaWdodChub2RlKV0pCgl7CgkJbWF4W25vZGVdPW1heFtsZWZ0KG5vZGUpXTsKCX0KCWVsc2UKCXsKCQltYXhbbm9kZV09bWF4W3JpZ2h0KG5vZGUpXTsKCX0KfQogCmludCBtaW5xdWVyeShpbnQgbm9kZSxpbnQgc3RhcnQsaW50IGVuZCxpbnQgcXN0YXJ0LGludCBxZW5kKQp7CglpbnQgbWlubGVmdCxtaW5yaWdodDsKIAoJaWYocXN0YXJ0PmVuZCB8fCBxZW5kPHN0YXJ0KQoJewoJCXJldHVybiAtMTsKCX0KIAoJaWYoc3RhcnQ+PXFzdGFydCAmJiBlbmQ8PXFlbmQpCgl7CgkJcmV0dXJuIG1pbltub2RlXTsKCX0KIAoJbWlubGVmdD1taW5xdWVyeShsZWZ0KG5vZGUpLGxlZnRzZWdtZW50KHN0YXJ0LGVuZCkscXN0YXJ0LHFlbmQpOwoJbWlucmlnaHQ9bWlucXVlcnkocmlnaHQobm9kZSkscmlnaHRzZWdtZW50KHN0YXJ0LGVuZCkscXN0YXJ0LHFlbmQpOwogCglpZihtaW5sZWZ0PT0tMSkKCXsKCQlyZXR1cm4gbWlucmlnaHQ7Cgl9CglpZihtaW5yaWdodD09LTEpCgl7CgkJcmV0dXJuIG1pbmxlZnQ7Cgl9CglpZihtaW5sZWZ0PD1taW5yaWdodCkKCXsKCQlyZXR1cm4gbWlubGVmdDsKCX0KCXJldHVybiBtaW5yaWdodDsKfQogCmludCBtYXhxdWVyeShpbnQgbm9kZSxpbnQgc3RhcnQsaW50IGVuZCxpbnQgcXN0YXJ0LGludCBxZW5kKQp7CglpbnQgbWF4bGVmdCxtYXhyaWdodDsKIAoJaWYocXN0YXJ0PmVuZCB8fCBxZW5kPHN0YXJ0KQoJewoJCXJldHVybiAtMTsKCX0KIAoJaWYoc3RhcnQ+PXFzdGFydCAmJiBlbmQ8PXFlbmQpCgl7CgkJcmV0dXJuIG1heFtub2RlXTsKCX0KIAoJbWF4bGVmdD1tYXhxdWVyeShsZWZ0KG5vZGUpLGxlZnRzZWdtZW50KHN0YXJ0LGVuZCkscXN0YXJ0LHFlbmQpOwoJbWF4cmlnaHQ9bWF4cXVlcnkocmlnaHQobm9kZSkscmlnaHRzZWdtZW50KHN0YXJ0LGVuZCkscXN0YXJ0LHFlbmQpOwogCglpZihtYXhsZWZ0PT0tMSkKCXsKCQlyZXR1cm4gbWF4cmlnaHQ7Cgl9CglpZihtYXhyaWdodD09LTEpCgl7CgkJcmV0dXJuIG1heGxlZnQ7Cgl9CglpZihtYXhsZWZ0Pj1tYXhyaWdodCkKCXsKCQlyZXR1cm4gbWF4bGVmdDsKCX0KCXJldHVybiBtYXhyaWdodDsKfQogCmludCBtYWluKGludCBhcmdjLCBjaGFyICoqYXJndikKewoJaW50IE4sUSxpLG1pbjEsbWF4MSxtYXgyLG1heDMsbCxyOwoJZG91YmxlIHQxLHQyLHQzLGFuczsKIAoJc2NhbmYoIiVkIiwmTik7Cglmb3IoaT0wO2k8TjtpKyspCgl7CgkJc2NhbmYoIiVkIiwmQVtpXSk7Cgl9CiAKCWluaXRpYWxpemUoMCwwLE4tMSk7CiAKCWZvcihzY2FuZigiJWQiLCZRKTtRPjA7US0tKQoJewoJCXNjYW5mKCIlZCVkIiwmbCwmcik7CiAKCQltaW4xPW1pbnF1ZXJ5KDAsMCxOLTEsbCxyKTsKCQltYXgxPW1heHF1ZXJ5KDAsMCxOLTEsbCxyKTsKCQltYXgxLT1taW4xOwoJCW1heDI9bWF4cXVlcnkoMCwwLE4tMSwwLGwtMSk7CgkJbWF4Mz1tYXhxdWVyeSgwLDAsTi0xLHIrMSxOLTEpOwogCgkJYW5zPW1pbjE7CgkJdDE9bWF4MS8yLjA7CgkJdDI9bWF4MjsKCQl0Mz1tYXgzOwogCgkJaWYodDI8dDMpdDI9dDM7CgkJaWYodDE8dDIpdDE9dDI7CiAKCQlhbnMrPXQxOwogCgkJcHJpbnRmKCIlLjFsZlxuIixhbnMpOwoJfQogCglyZXR1cm4gMDsKfQ==