# include <cstdio>
# define N 100010

using namespace std;

int n,type,k,st,dr,m,poz,mij;
int a[N];

inline int caut_jos()
{
    poz=-1;
    st=1;
    dr=n;
    while(st<=dr)
    {
        mij=(st+dr)>>1;
        if(a[mij]<k) st=mij+1;
        else if(a[mij]>k) dr=mij-1;
        else poz=mij, dr=mij-1;
    }

    if(poz!=-1) return poz;
    else return st;
}

inline int caut_sus()
{
    poz=-1;
    st=1;
    dr=n;
    while(st<=dr)
    {
        mij=(st+dr)>>1;
        if(a[mij]<k) st=mij+1;
        else if(a[mij]>k) dr=mij-1;
        else poz=mij, st=mij+1;
    }

    if(type==0) return poz;
    else if(poz!=-1) return poz;
    else return dr;
}

int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);

    scanf("%d\n", &n);
    for(int i=1; i<=n; ++i)
        scanf("%d", &a[i]);

    scanf("%d\n", &m);
    for(int i=1; i<=m; ++i)
    {
        scanf("%d %d\n", &type, &k);
        if(type==0) printf("%d\n", caut_sus());
        if(type==1) printf("%d\n", caut_sus());
        if(type==2) printf("%d\n", caut_jos());
    }

    return 0;
}