#include<stdio.h>
#define DIM 100001
int a[DIM],x,q,n,m;
int cbin1 (int x)
{
	int in=1,sf=n,mij;
	while(in<=sf)
	{
		mij=(in+sf)/2;
        if(x==a[mij])
            return mij;
        else if (x<a[mij])
            sf=mij-1;
        else
            in=mij+1;
	}
    return -1;        
}
int cbin2 (int x)
{
	int in=1,sf=n,mij,nr=0;
    while(in<=sf)
	{
		mij=(in+sf)/2;
		if (x<a[mij])
			sf=mij-1;
		else
		{
			nr=mij;
			in=mij+1;
		}
	}
	return nr;
}
int cbin3 (int x)
{
	int in=1,sf=n,mij,nr=n+1;
	while(in<=sf)
	{
		mij=(in+sf)/2;
		if (x<a[mij])
        {
            nr=mij;
            sf=mij-1;
        }
        else
            in=mij+1;
    }
    return nr;        
}
int main ()
{
    freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%d",&a[i]);
    scanf("%d",&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&q,&x);
        if(q==0)
            printf("%d\n",cbin1 (x));
        else if(q==1)
            printf("%d\n",cbin2 (x));
        else
            printf("%d\n",cbin3 (x));
    }    
    return 0;
}