#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
/*
Declare pointers instead of arrays
*/
int *min;
int *max;
int *A;
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;
/*
Allocate N blocks to all arrays
*/
A
=(int *)calloc(N
,sizeof(int)); min
=(int *)calloc(N
,sizeof(int)); max
=(int *)calloc(N
,sizeof(int)); 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+CiNpbmNsdWRlIDxzdGRsaWIuaD4KIAojZGVmaW5lIGxlZnQoYSkgKChhKjIpKzEpCiNkZWZpbmUgcmlnaHQoYSkgKChhKjIpKzIpCiAKI2RlZmluZSBsZWZ0c2VnbWVudChzdGFydCxlbmQpIHN0YXJ0LChzdGFydCtlbmQpLzIKI2RlZmluZSByaWdodHNlZ21lbnQoc3RhcnQsZW5kKSAoKHN0YXJ0K2VuZCkvMikrMSxlbmQKCi8qCglEZWNsYXJlIHBvaW50ZXJzIGluc3RlYWQgb2YgYXJyYXlzCiovCgppbnQgKm1pbjsKaW50ICptYXg7CmludCAqQTsKIAp2b2lkIGluaXRpYWxpemUoaW50IG5vZGUsaW50IHN0YXJ0LGludCBlbmQpCnsKCWlmKHN0YXJ0PT1lbmQpCgl7CgkJbWluW25vZGVdPUFbc3RhcnRdOwoJCW1heFtub2RlXT1BW3N0YXJ0XTsKCQlyZXR1cm47Cgl9CiAKCWluaXRpYWxpemUobGVmdChub2RlKSxsZWZ0c2VnbWVudChzdGFydCxlbmQpKTsKCWluaXRpYWxpemUocmlnaHQobm9kZSkscmlnaHRzZWdtZW50KHN0YXJ0LGVuZCkpOwogCglpZihtaW5bbGVmdChub2RlKV08PW1pbltyaWdodChub2RlKV0pCgl7CgkJbWluW25vZGVdPW1pbltsZWZ0KG5vZGUpXTsKCX0KCWVsc2UKCXsKCQltaW5bbm9kZV09bWluW3JpZ2h0KG5vZGUpXTsKCX0KIAoJaWYobWF4W2xlZnQobm9kZSldPj1tYXhbcmlnaHQobm9kZSldKQoJewoJCW1heFtub2RlXT1tYXhbbGVmdChub2RlKV07Cgl9CgllbHNlCgl7CgkJbWF4W25vZGVdPW1heFtyaWdodChub2RlKV07Cgl9Cn0KIAppbnQgbWlucXVlcnkoaW50IG5vZGUsaW50IHN0YXJ0LGludCBlbmQsaW50IHFzdGFydCxpbnQgcWVuZCkKewoJaW50IG1pbmxlZnQsbWlucmlnaHQ7CiAKCWlmKHFzdGFydD5lbmQgfHwgcWVuZDxzdGFydCkKCXsKCQlyZXR1cm4gLTE7Cgl9CiAKCWlmKHN0YXJ0Pj1xc3RhcnQgJiYgZW5kPD1xZW5kKQoJewoJCXJldHVybiBtaW5bbm9kZV07Cgl9CiAKCW1pbmxlZnQ9bWlucXVlcnkobGVmdChub2RlKSxsZWZ0c2VnbWVudChzdGFydCxlbmQpLHFzdGFydCxxZW5kKTsKCW1pbnJpZ2h0PW1pbnF1ZXJ5KHJpZ2h0KG5vZGUpLHJpZ2h0c2VnbWVudChzdGFydCxlbmQpLHFzdGFydCxxZW5kKTsKIAoJaWYobWlubGVmdD09LTEpCgl7CgkJcmV0dXJuIG1pbnJpZ2h0OwoJfQoJaWYobWlucmlnaHQ9PS0xKQoJewoJCXJldHVybiBtaW5sZWZ0OwoJfQoJaWYobWlubGVmdDw9bWlucmlnaHQpCgl7CgkJcmV0dXJuIG1pbmxlZnQ7Cgl9CglyZXR1cm4gbWlucmlnaHQ7Cn0KIAppbnQgbWF4cXVlcnkoaW50IG5vZGUsaW50IHN0YXJ0LGludCBlbmQsaW50IHFzdGFydCxpbnQgcWVuZCkKewoJaW50IG1heGxlZnQsbWF4cmlnaHQ7CiAKCWlmKHFzdGFydD5lbmQgfHwgcWVuZDxzdGFydCkKCXsKCQlyZXR1cm4gLTE7Cgl9CiAKCWlmKHN0YXJ0Pj1xc3RhcnQgJiYgZW5kPD1xZW5kKQoJewoJCXJldHVybiBtYXhbbm9kZV07Cgl9CiAKCW1heGxlZnQ9bWF4cXVlcnkobGVmdChub2RlKSxsZWZ0c2VnbWVudChzdGFydCxlbmQpLHFzdGFydCxxZW5kKTsKCW1heHJpZ2h0PW1heHF1ZXJ5KHJpZ2h0KG5vZGUpLHJpZ2h0c2VnbWVudChzdGFydCxlbmQpLHFzdGFydCxxZW5kKTsKIAoJaWYobWF4bGVmdD09LTEpCgl7CgkJcmV0dXJuIG1heHJpZ2h0OwoJfQoJaWYobWF4cmlnaHQ9PS0xKQoJewoJCXJldHVybiBtYXhsZWZ0OwoJfQoJaWYobWF4bGVmdD49bWF4cmlnaHQpCgl7CgkJcmV0dXJuIG1heGxlZnQ7Cgl9CglyZXR1cm4gbWF4cmlnaHQ7Cn0KIAppbnQgbWFpbihpbnQgYXJnYywgY2hhciAqKmFyZ3YpCnsKCWludCBOLFEsaSxtaW4xLG1heDEsbWF4MixtYXgzLGwscjsKCWRvdWJsZSB0MSx0Mix0MyxhbnM7CiAKCXNjYW5mKCIlZCIsJk4pOwovKgoJQWxsb2NhdGUgTiBibG9ja3MgdG8gYWxsIGFycmF5cwoqLwoJQT0oaW50ICopY2FsbG9jKE4sc2l6ZW9mKGludCkpOwoJbWluPShpbnQgKiljYWxsb2MoTixzaXplb2YoaW50KSk7CgltYXg9KGludCAqKWNhbGxvYyhOLHNpemVvZihpbnQpKTsKCWZvcihpPTA7aTxOO2krKykKCXsKCQlzY2FuZigiJWQiLCZBW2ldKTsKCX0KIAoJaW5pdGlhbGl6ZSgwLDAsTi0xKTsKIAoJZm9yKHNjYW5mKCIlZCIsJlEpO1E+MDtRLS0pCgl7CgkJc2NhbmYoIiVkJWQiLCZsLCZyKTsKIAoJCW1pbjE9bWlucXVlcnkoMCwwLE4tMSxsLHIpOwoJCW1heDE9bWF4cXVlcnkoMCwwLE4tMSxsLHIpOwoJCW1heDEtPW1pbjE7CgkJbWF4Mj1tYXhxdWVyeSgwLDAsTi0xLDAsbC0xKTsKCQltYXgzPW1heHF1ZXJ5KDAsMCxOLTEscisxLE4tMSk7CiAKCQlhbnM9bWluMTsKCQl0MT1tYXgxLzIuMDsKCQl0Mj1tYXgyOwoJCXQzPW1heDM7CiAKCQlpZih0Mjx0Myl0Mj10MzsKCQlpZih0MTx0Mil0MT10MjsKIAoJCWFucys9dDE7CiAKCQlwcmludGYoIiUuMWxmXG4iLGFucyk7Cgl9CiAKCXJldHVybiAwOwp9