#include<stdio.h>
#include<stdlib.h>
int *v, x,poz;
int search(int st,int dr,int q)
{  poz=-1;
	int m;
	while(dr>=st)
	     {m=st+(dr-st)/2; 
	      if(q==0)
		    {if(x==v[m]) poz=m;
		     if(x<v[m]) dr=m-1;
		  	 else st=m+1; continue;
		    }
		  if(q==1)
		    {if(v[m]<=x)    poz=m,st=m+1;
		     else dr=m-1; continue;
		    }
		  if(q==2)
		    {if(v[m]>=x) poz=m,dr=m-1;
		     else st=m+1; continue ;
		    }
	    }
	return poz;
}
int main()
{       register int i;
	int n,m,q;
	freopen("cautbin.in","rt",stdin);
	freopen("cautbin.out","wt",stdout);
	scanf("%d",&n); v=(int*)calloc(n+1,sizeof(n)); 	
	for(i=1;i<=n;++i) scanf("%d",&v[i]);
	scanf("%d",&m); 
	while(m)
	{   scanf("%d%d",&q,&x); 
		printf("%d\n",search(1,n,q)); 
	    --m;
	} free(v);
	return 0;
}