#include<stdio.h>
#define DIM 100001
int a[DIM],x,q,n,m;
int cbin1 (int x)
{
    int in,sf,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,sf,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,sf,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;
}