#include <stdio.h>
int main ()
{ FILE *f=fopen("cautbin.in","r");
FILE *g=fopen("cautbin.out","w");
long long i,n,v[100001],m,st,dr,mij,x,y,ok,p;
fscanf (f,"%lld",&n);
for (i=1; i<=n; i++)
	fscanf (f,"%lld",&v[i]);
fscanf (f,"%lld",&m);
for (i=1; i<=m; i++)
	{ fscanf (f,"%lld %lld",&x,&y);
        st=1;
	  dr=n;
	  ok=0;
        if (x==0) { while (st<=dr && ok==0)
				{ mij=(st+dr)/2;
		              if (y==v[mij] && (v[mij+1]!=y || mij+1>n)) { ok=1; p=mij;}
				  else if (v[mij]<=y) st=mij+1;
					  else dr=mij-1;
				}
			  if (ok) fprintf (g,"%lld\n",p);
			  else fprintf(g,"-1\n");
			}
	  else if (x==1) { p=1;
	                   while (st<=dr && ok==0)
					   { mij=(st+dr)/2;
					     if (y>=v[mij] && (v[mij+1]>y || mij+1>n)) { p=mij; ok=1;}
					     else if (y<v[mij]) dr=mij-1;
						    else st=mij+1;
					   }
				 fprintf(g,"%lld\n",p);
				  }
	       else { p=1;
		        while (st<=dr && ok==0)
				{ mij=(st+dr)/2;
				  if (y<=v[mij] && (v[mij-1]<y || mij-1==0)) { p=mij; ok=1;}
				  else if (y<=v[mij]) dr=mij-1;
						    else st=mij+1;
				 }
			  fprintf(g,"%lld\n",p);
		   }
	}
fclose (f);
fclose (g);
return 0;
}