int query(int level,int left,int right,int qleft,int qright,int k){
if( qleft==qright)
return tree[level][qleft];
int s;//代表[left,qleft)之间有多个个元素被分到左边
int ss;//[qleft, qright]内将被划分到左子树的元素数目
int mid=(left+right)>>1;
if(left==qleft){
s=0;
ss=toLeft[level][qright];
}else{
s=toLeft[level][qleft-1];
ss=toLeft[level][qright]-s;
}
int newl,newr;
if(k<=ss){//查询左边
newl=left+s;
newr=left+s+ss-1;
return query(level+1,left,mid,newl,newr,k);
}else{//查询右边
newl=mid-left+1+qleft-s;
newr=mid-left+1+qright-s-ss;
return query(level+1,mid+1,right,newl, newr,k - ss);
}
}
int n,m,cas=0;
while(scanf("%d",&n)!=EOF)
{
cas++;
printf("Case %d:\n",cas);
int i;
for(i=1;i<=n;i++){
scanf("%d",&tree[0][i]);
sorted[i]=tree[0][i];
}
sort(sorted+1,sorted+n+1);
build(0,1,n);
scanf("%d",&m);
int ql,qr,k;
for(i=0;i
scanf("%d %d",&ql,&qr);
k=(qr-ql)/2+1;
printf("%d\n",query(0,1,n,ql,qr,k));
}
}
return 0;
}