#include<cstdio>
using namespace std;
long int x,m,b,c,d,f,i,g,k,l,n,val,a[100000];
int lol(long int x, long int y,long int z){
	 long int medie;
	 while (x<=y){
		 medie=(x+y)/2;
		 if(a[medie]<=z)
			 x=medie+1;
		 else
			y=medie-1;}
	 medie=(x+y)/2;
	 if(a[medie]>z)
		 medie--;
	 if(a[medie]==z)
		 return medie;
	 return -1;}
int lol1(long int x, long int y,long int z){
	 long int medie;
	 while (x<y){
		  medie=(x+y)/2;
		 if(a[medie]<=z)
			 x=medie+1;
		 else
			y=medie-1;}
		medie=(x+y)/2;
		if(a[medie]>z)
		 medie--;
		
		return medie;}
		
int lol2(long int x, long int y,long int z){
	 long int medie;
	 while (x<y){
		  medie=(x+y)/2;
		 if(a[medie]>=z)
			 y=medie-1;
		 else
			x=medie+1;}
		medie=(x+y)/2;
		if(a[medie]<z)
		 medie++;
		
		return medie;}
int main(){
	freopen ("cautbin.in","r",stdin);
	freopen ("cautbin.out","w",stdout);
	scanf("%lld ",&n);
	
	for(i=1;i<=n;i++)
	scanf("%ld ",&a[i]);
	scanf("%ld ",&m);
	while(m--){
		scanf("%ld %ld",&i ,&val);
		if(i==0)
			printf("%ld\n",lol(1,n,val));
		if(i==1)
			printf("%ld\n",lol1(1,n,val));
		if(i==2)
			printf("%ld\n",lol2(1,n,val));
	}
	return 0;}