#include <stdio.h>
#define Nmax 100005

int a[Nmax];
long n,m,i,k,poz,tip,x,rez;

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

long cauta1(long st,long dr,long x){
	long mij;
   while(st<=dr){
   	mij=dr+(st-dr)/2;
      if(x>=a[mij]) poz=mij,st=mij+1;
      else dr=mij-1;
   }
   return poz;
}

long cauta2(long st,long dr,long x){
	long mij;
   while(st<=dr){
   	mij=dr+(st-dr)/2;
      if(x<=a[mij]) poz=mij,dr=mij-1;
      else st=mij+1;
   }
   return poz;
}

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