#include<cstdio>
using namespace std;
FILE *f,*g;
int i,n,a,b,m,mij,ls,ld,x,v[100001];
int main()
{f=fopen("cautbin.in","r");
g=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",&b,&a);
if(b==0)
{ls=1; ld=n;
while(ls<=ld)
{mij=(ld+ls)/2;
if(a>=v[mij])
	ls=mij+1;
else
	ld=mij-1;
}
if(v[ld]==a)
	fprintf(g,"%d\n",ld);
else
	fprintf(g,"-1\n");
}
else
	if(b==1)
	{ls=1; ld=n; x=-1;
	mij=(ld+ls)/2;
	while(ls<=ld)
	{if(a>=v[mij])
		ls=mij+1;
	else
		ld=mij-1;
	mij=(ld+ls)/2;
	}
	fprintf(g,"%d\n",ld);
	}
	else
		if(b==2)
		{ls=1; ld=n;
	    mij=(ld+ls)/2;
	    while(ls<=ld)
	    {if(a<=v[mij])
		    ld=mij-1;
	    else
			ls=mij+1;
	    mij=ls+(ld-ls)/2;
	    }
		fprintf(g,"%d\n",ls);
	    }
}
return 0;
}