#include<stdio.h>
int *a,m,n,x,y;
int bin0(int x,int p,int u)
{
    int m,gasit=-1,st=p,dr=u;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if (a[m]==x)
        {
            gasit=m;
            st=m+1;
        }
		else
        if(a[m]<x)
            st=m+1;
        else
            dr=m-1;
    }
        return gasit;
}

int bin1(int x,int p,int u)
{
	int m, gasit,st=p,dr=u;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if (a[m]<=x)
        {
            gasit=m;
            st=m+1;
        }
        else
            dr=m-1;
    }
    return gasit;
}

int bin2(int x,int p,int u)
{
    int m,gasit,st=p,dr=u;
    while(st<=dr)
    {
    m=(st+dr)/2;
    if (a[m]>=x)
    {
        gasit=m;
        dr=m-1;
    }
    else
		st=m+1;
    }
    return gasit;
}
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d", &n);
	a=new int[n+1];
	for(int i=1;i<=n;i++)
		scanf("%d", &a[i]);
	scanf("%d\n", &m);
	while(m)
	{
		m--;
		scanf("%d %d", &y, &x);
		if(y==0)
			printf("%d\n",bin0(x,1,n));
		else
			if(y==1)
				printf("%d\n",bin1(x,1,n));
			else
				printf("%d\n",bin2(x,1,n));
	}
	return 0;
}