#include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <vector>

 #include <algorithm>

 #include <set>

 #define repu(i,a,b) for(int i=a;i<b;i++)

 using namespace std;

 #define N 1000010

 #define ll long long

 #define _cle(m, a) memset(m, a, sizeof(m))

 const int MAXN = ;

 const int M = MAXN * ;

 int n,q,m,tot;

 int a[MAXN], t[MAXN];

 int T[MAXN], lson[M], rson[M], c[M];

 void Init_Hash()

 {

     for(int i = ; i <= n; i++)

         t[i] = a[i];

     sort(t+,t++n);

     m = unique(t+,t++n) -t-;

 }

 int build(int l, int r)

 {

     int root = tot++;

     c[root] = ;

     if(l != r)

     {

         int mid = (l+r)>>;

         lson[root] = build(l,mid);

         rson[root] = build(mid+,r);

     }

     return root;

 }

 int Hash(int x)

 {

     return lower_bound(t+,t++m,x) - t;

 }

 int update(int root, int pos, int val)

 {

     int newroot = tot++, tmp = newroot;

     c[newroot] = c[root] + val;

     int l = , r = m;

     while(l < r)

     {

         int mid = (l+r)>>;

         if(pos <= mid)

         {

             lson[newroot] = tot++;

             rson[newroot] = rson[root];

             newroot = lson[newroot];

             root = lson[root];

             r = mid;

         }

         else

         {

             rson[newroot] = tot++;

             lson[newroot] = lson[root];

             newroot = rson[newroot];

             root = rson[root];

             l = mid+;

         }

         c[newroot] = c[root] + val;

     }

     return tmp;

 }

 int query(int left_root, int right_root, int k)

 {

     int l = , r = m;

     while( l < r)

     {

         int mid = (l+r)>>;

         if(c[lson[left_root]] -c[lson[right_root]] >= k )

         {

             r = mid;

             left_root = lson[left_root];

             right_root = lson[right_root];

         }

         else

         {

             l = mid + ;

             k -= c[lson[left_root]] - c[lson[right_root]];

             left_root = rson[left_root];

             right_root = rson[right_root];

         }

     }

     return l;

 }

 int main()

 {

 //freopen("in.txt","r", stdin);

 //freopen("out.txt","w", stdout);

     int kase = ;

     while(scanf("%d",&n) == )

     {

         tot = ;

         for(int i = ; i <= n; i++)

             scanf("%d",&a[i]);

         Init_Hash();

         T[n+] = build(,m);

         for(int i = n; i ; i--)

         {

             int pos = Hash(a[i]);

             T[i] = update(T[i+],pos,);

         }

         printf("Case %d:\n",kase++);

         scanf("%d",&q);

         while(q--)

         {

             int l,r,k;

             scanf("%d%d",&l,&r);

             k = (r-l)/+;

             printf("%d\n",t[query(T[l],T[r+],k)]);

         }

     }

     return ;

 }

 //划分树

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int MAXN=;

 int tree[][MAXN];//表示每层每个位置的值

 int sorted[MAXN];//已经排序好的数

 int toleft[][MAXN];//toleft[p][i]表示第i层从1到i有数分入左边

 void build(int l,int r,int dep){

     if(l==r)return;

     int mid=(l+r)>>;

     int same=mid-l+;//表示等于中间值而且被分入左边的个数

     for(int i=l;i<=r;i++)//注意是l,不是one

         if(tree[dep][i]<sorted[mid]) same--;

     int lpos=l;

     int rpos=mid+;

     for(int i=l;i<=r;i++){

         if(tree[dep][i]<sorted[mid]) tree[dep+][lpos++]=tree[dep][i];

         else if(tree[dep][i]==sorted[mid]&&same>){

             tree[dep+][lpos++]=tree[dep][i];

             same--;

         }

         else tree[dep+][rpos++]=tree[dep][i];

         toleft[dep][i]=toleft[dep][l-]+lpos-l;

     }

     build(l,mid,dep+);

     build(mid+,r,dep+);

 }

 //查询区间第k大的数,[L,R]是大区间,[l,r]是要查询的小区间

 int query(int L,int R,int l,int r,int dep,int k){

     if(l==r)return tree[dep][l];

     int mid=(L+R)>>;

     int cnt=toleft[dep][r]-toleft[dep][l-];

     if(cnt>=k){

         int newl=L+toleft[dep][l-]-toleft[dep][L-];int newr=newl+cnt-;

         return query(L,mid,newl,newr,dep+,k);

     }

     else{

         int newr=r+toleft[dep][R]-toleft[dep][r],newl=newr-(r-l-cnt);

         return query(mid+,R,newl,newr,dep+,k-cnt);

     }

 }

 int main(){

     int n,m,t=;

     while(~scanf("%d",&n)){

         memset(tree,,sizeof(tree));

         for(int i=;i<=n;i++){

             scanf("%d",&tree[][i]);

             sorted[i]=tree[][i];

         }

         sort(sorted+,sorted+n+);

         build(,n,);

         scanf("%d",&m);

         printf("Case %d:\n",++t);

         int s,t,k;

         while(m--){

             scanf("%d%d",&s,&t);

             k=(t-s+)/;

             printf("%d\n",query(,n,s,t,,k));

         }

     }

     return ;

 }