#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(long long val)
{ int i, step;  
  for (step = 1; step < n; step <<= 1);
  for (i = 0; step; step >>= 1)  
        if (i + step < n && a[i + step] <= val)
           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;
}