#include<stdio.h>
#include<stdlib.h>
int *v, x,poz;
inline int search(int st,int dr,int q)
{
	if(dr>=st)
	  {
		  int m=st+(dr-st)/2;
		  if(q==0)
		    {if(x==v[m]) poz=m;
		     if(x<v[m]) return search(st,m-1,q);
			 return search(m+1,dr,q);
		   }else if(q==1)
		           {if(v[m]<=x)poz=m;
		            if(v[m]<=x) return search(m+1,dr,q);
					return search(st,m-1,q);
		           }else {if(v[m]>=x) poz=m;
				          if(v[m]>=x) return search(st,m-1,q);
						  return search(m+1,dr,q);
						  }
	}
	return poz;
}
int main()
{
	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(register unsigned i=1;i<=n;++i) scanf("%d",&v[i]);
	scanf("%d",&m);
	while(m)
	{   poz=-1;
		scanf("%d%d",&q,&x);
		printf("%d\n",search(1,n,q)); 
	    --m;
	}
	return 0;
}