#include <stdio.h>

FILE *f,*s;

int m,n,i;

int v[100005];

int a,b;

int Cauta1()
{
	int st=1;
	int dr=n;
	
	int mj;
	
	int sol=-1;
	
	while(st<=dr)
	{
		mj=(st+dr)/2;
		
		if(v[mj]<=b)
		{
			if(v[mj]==b) sol=mj;
			
			st=mj+1;
		}
		
		else if(v[mj]>b)
			dr=mj-1;
	}
	
	return sol;
}

int Cauta2()
{
	int st=1;
	int dr=n;
	
	int mj;
	
	int sol=-1;
	
	while(st<=dr)
	{
		mj=(st+dr)/2;
		
		if(v[mj]<=b)
		{
			sol=mj;
			
			st=mj+1;
		}
		else if(v[mj]>=b)
			dr=mj-1;
	}
	
	return sol;
}

int Cauta3()
{
	int st=1;
	int dr=n;
	
	int mj;
	
	int sol=1;
	
	while(st<=dr)
	{
		mj=(st+dr)/2;
		
		if(v[mj]>=b)
		{
			sol=mj;
			
			dr=mj-1;
		}
		
		else if(v[mj]<b)
			st=mj+1;
	}
	
	return sol;
}

int main()
{
	f=fopen("cautbin.in","r");
	s=fopen("cautbin.out","w");
	
	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,&b);
		
		if(a==0) fprintf(s,"%d\n",Cauta1());
		if(a==1) fprintf(s,"%d\n",Cauta2());
		if(a==2) fprintf(s,"%d\n",Cauta3());	
	}
	
	fclose(s);
	
	return 0;
}