#include<cstdio>
using namespace std;
long n,v[100005];

long bsdr(long x)
{
	long st=1,dr=n,last=1,med;
	while(st<=dr)
	{
		med=st+((dr-st)>>1);
		if(v[med]<=x)
		{
			last=med;
			st=med+1;
		}
		else
			dr=med-1;
	}
	return last;
}
long bsst(long x)
{
    long st,dr,med,last=1;
    st=1;
    dr=n;
    while(st<=dr)
    {
        med=st+((dr-st)>>1);
        if(x>v[med])
            st=med+1;
        else
        if(x<=v[med])
            {
                dr=med-1;
                last=med;
            }
    }
    return last;
}
long i,x,poz,t,m;
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%ld",&n);
	for(i=1;i<=n;i++)
		scanf("%ld",&v[i]);
	scanf("%ld",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%ld%ld",&t,&x);
		if(t==0)
		{
			poz=bsdr(x);
			if(v[poz]==x)
				printf("%ld\n",poz);
			else
				printf("-1");
		}
		else if(t==1)
			printf("%ld\n",bsdr(x));
		else
			if(t==2)
				printf("%ld\n",bsst(x));
	}
	return 0;
}