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