#include<stdio.h>
FILE *f=fopen("cautbin.in","r"),
     *g=fopen("cautbin.out","w");
long long i,j,m,n,a[100001],x,k;
int bs(int k)
{ int step;
  for(step=1;step<=n;step<<=1);
  int i;
  for(i=0;step;step>>=1)
    if(i+step<=n&&a[i+step]<=k) i+=step;
  return i;
}
int main()
{ fscanf(f,"%lld",&n);
  for(i=1;i<=n;++i) fscanf(f,"%lld",&a[i]);
  fscanf(f,"%lld",&m);
  for(i=1;i<=m;++i)
  { fscanf(f,"%lld %lld",&j,&x);
    k=bs(x);
    if(j==0) { while(a[k]==x) ++k;
	       if(a[k-1]==x) fprintf(g,"%lld\n",k-1);
	       else fprintf(g,"-1\n");
	     }
    else if(j==1){ while(a[k]>x) --k;
		   fprintf(g,"%lld\n",k);
		 }
    else { while(a[k]<x) ++k;
	   fprintf(g,"%lld\n",k);
	 }
  }
  fclose(f);
  fclose(g);
  return 0;
}