#include<stdio.h>

int n,m,a[100001],i;
int search0(int x)
{
	int l=1,r=n,m,sol=-1;
    while(l<=r)
    {
        m=(l+r)/2;
        if(a[m]==x)
            sol=m;
        if(a[m]>x)
            r=m-1;
        else
            l=m+1;
    }
    return sol;
}

int search1(int x)
{
    int l=1,r=n,m,sol;
    while(l<=r)
    {
        m=(l+r)/2;
        if(a[m]<=x)
        {
            sol=m;
            l=m+1;
        }
        else
            r=m-1;
    }
    return sol;
}
int search2(int x)
{
    int l=1,r=n,m,sol;
    while(l<=r)
    {
        m=(l+r)/2;
        if(a[m]>=x)
        {
            sol=m;
            r=m-1;
        }
        else
            l=m+1;
    }
    return sol;
}
int main()
{
	int k,a1,b;
	FILE *f=fopen("cautbin.in","r");
	FILE *g=fopen("cautbin.out","w");

	fscanf (f,"%d",&n);
	for (i=1;i<=n;i++)
		fscanf (f,"%d",&a[i]);
	
	fscanf (f,"%d",&k);
	for (i=1;i<=k;i++)
	{
		fscanf (f,"%d%d",&a1,&b);
		if (a1==0)
			fprintf(g,"%d\n",search0(b));
		else
			if (a1==1)
				fprintf(g,"%d\n",search1(b));
			else
				fprintf(g,"%d\n",search2(b));
	}

	return 0;
}