#include <stdio.h>
int a[100000],n,m;
int bin1(int nr)
{ int lo=1,hi=n,mid;
	while(lo<=hi)
     { mid=lo+(hi-lo)/2;
	if(a[mid]==nr)
		return mid;
	else if(a[mid]<nr) lo=mid+1;
	else if(a[mid]>nr) hi=mid-1;
	     }
 return -1;
}
int bin2(int nr)
{ int lo=1,hi=n,mid;
	while(lo<=hi)
	{ mid=lo+(hi-lo)/2;
	 if(a[mid]<=nr) {nr=mid;lo=mid+1;}
	 else hi=mid-1;
	 
	}
   return nr;
}
int bin3(int nr)
{ int lo=1,hi=n,mid;
	while(lo<=hi)
	{ mid=lo+(hi-lo)/2;
	if(a[mid]>=nr){ nr=mid;hi=mid-1;}
	else lo=mid+1;
	}
   return nr;
   }
int main()
{  int b,x,i;
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
scanf("%d",&n);
for( i=1;i<=n;i++)
	{scanf("%d",&a[i]);}
 scanf("%d",&m);
 for(i=1;i<=m;i++)
	{scanf("%d %d", &b,&x);
	 if(b==0) printf("%d",bin1(x));
	 else if(b==1) printf("%d",bin2(x));
	 else printf("%d",bin3(x));}
return 0;
}