#include<stdio.h>
FILE *f,*g;
long long a[100100],i,j,mij,l1,l2,ok,x,y,m,n;
int main()
{ f=fopen("cautbin.in","r"); g=fopen("cautbin.out","w");
  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",&x,&y);
     l1=1; l2=n; ok=1;
	 while(l1<=l2&&ok)
	  { mij=(l1+l2)/2;
	    if(a[mij]==y) ok=0;
		else if(a[mij]>x) l2=mij-1;
		else l1=mij+1;
	  }
	 if(x==0)
        { if(ok) fprintf(g,"-1\n");
		  else { j=mij; while(a[j+1]==y) j++; fprintf(g,"%ld\n",j); }
		}
	if(x==1)
	    {  if(a[mij]<=y) { j=mij; while(a[j+1]<=y) j++; fprintf(g,"%ld\n",j); }
		   else { j=mij; while(a[j-1]>y) j--; j--; fprintf(g,"%ld\n",j); }
		}
	if(x==2)
	    {  if(a[mij]>=y) { j=mij; while(a[j-1]>=y) j--; fprintf(g,"%ld\n",j); }
		   else { j=mij; while(a[j+1]<y) j++; j++; fprintf(g,"%ld\n",j); }
		}
   }
  fclose(g);
  return 0;
}