#include<cstdio>
int a[100001], x, n, q;

int cauta0 (int x)
{ int st=1, dr=n, mij;
  mij=(n+1)/2;
  if(x<a[mij]) if(a[st]==x) return st;
               else ++st;
  else if(x==a[mij]) { while(x==a[mij]) mij++;
                       return --mij;
                     }
       else if(a[mij]==x) return mij; //while(a[mij++]<=a[dr])
	        else mij++;//  if(a[mij]==x) return mij;
  return -1;
  /*
  while(st<=dr) { if(a[st]<x) ++st;
                  if(a[dr]>x) --dr;
                  if(a[dr]==x) return dr;
                }
  return -1;*/
}  

int cauta1 (int x)
{ int dr=n;
  while(dr) if(a[dr]>x) --dr;
            else return dr;
}

int cauta2 (int x)
{ int st=1;
  while(st<=n) if(a[st]<x) ++st;
               else return st;
}
  


int main()
{ freopen("cautbin.in", "r", stdin);
  freopen("cautbin.out", "w", stdout);
  
  int k, i;
  scanf("%d", &n);
  for(i=1; i<=n; ++i) scanf("%d", &a[i]);
  scanf("%d", &q);
  while(q--) { scanf("%d %d", &k, &x);
               if(k==0) printf("%d\n", cauta0(x));
               else if(k==1) printf("%d\n", cauta1(x));
			        else printf("%d\n", cauta2(x));
             }
  return 0;
}