#include<stdio.h>
using namespace std;
int v[100001],n,m,x,i;

int caut_bin (int i, int in,int sf)
{
	   
	if(i>in) return i;  
	int mij=(i+((in-i)/2));   
		if(x==v[mij]) return mij;
		
		if(x>v[mij])
			return  caut_bin(mij+1,in,x); 
		else	
			return caut_bin(i,mij-1,x);
	
	}



int main()
{
	FILE *f=fopen("cautbin.in","r"), *g=fopen("cautbin.out","w");
	
	int m,a;
	
fscanf(f,"%d",&n);

for(i=1;i<=n;i++)
{
		fscanf(f,"%d",&v[i]);	
}
fscanf(f,"%d",&m);
for(i=1;i<=m;i++)
{
fscanf(f,"%d%d",&a,&x);
	if(a==0)
	{int poz=caut_bin(1,n,x);
	 if(v[poz]!=x)    poz=-1;
          fprintf(g,"%d\n",poz);                 
	}
	else if(a==1)
	{int poz=caut_bin(1,n,x);
	while(v[poz]<=x&&poz<=n) poz++;   
	fprintf(g,"%d\n",--poz);
	}
	else if(a==2)
	{int poz=caut_bin(1,n,x);
	while(v[poz]>=x&&poz>0) poz--;   
	fprintf(g,"%d\n",++poz);}
	
}

	
	
	
	
fclose(f);
fclose(g);

return 0;}