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

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

int caut_bin1 (int in,int sf)
{
	
	
		int mij=(in+sf)/2;
		if(x<=v[mij]) return mij;
		if(x<v[mij])
				return caut_bin1(in,mij-1);
				
		return caut_bin1(mij+1,sf);

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

int main()
{
	FILE *f=fopen("cautbin.in","r"), *g=fopen("cautbin.out","w");
	
	int i,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);
	fprintf(g,"%d\n",poz);
	}
	else if(a==1)
	{int poz=caut_bin1(1,n);
	fprintf(g,"%d\n",poz);}
	else if(a==2)
	{int poz=caut_bin2(1,n);
	fprintf(g,"%d\n",poz);}
	
}

	
	
	
	
fclose(f);
fclose(g);

return 0;}