#include <cstdio>
#define Nmax 100005

using namespace std;

int v[Nmax],N;

inline int BSearch1(int x)
{
    int st=1,dr=N,mij;
    while(st<=dr)
    {
        mij=((st+dr)>>1);
        if(v[mij]<=x)
            st=mij+1;
        else
            dr=mij-1;
    }
    mij=((st+dr)>>1);
    if(v[mij]>x)
        --mij;
    if(v[mij]!=x)
        return -1;
    return mij;
}

inline int BSearch2(int x)
{
    int st=1,dr=N,mij;
    while(st<=dr)
    {
        mij=((st+dr)>>1);
        if(v[mij]<=x)
            st=mij+1;
        else
            dr=mij-1;
    }
    mij=((st+dr)>>1);
    if(v[mij]>x)
        --mij;
    return mij;
}

inline int BSearch3(int x)
{
    int st=1,dr=N,mij;
    while(st<=dr)
    {
        mij=((st+dr)>>1);
        if(v[mij]<x)
            st=mij+1;
        else
            dr=mij-1;
    }
    mij=((st+dr)>>1);
    if(v[mij]<x)
        ++mij;
    return mij;
}

int main()
{
    int M,i,x,tip;
    freopen ("cautbin.in","r",stdin);
    freopen ("cautbin.out","w",stdout);
    scanf("%d", &N);
    for(i=1;i<=N;++i)
        scanf("%d", &v[i]);
    scanf("%d", &M);
    while(M--)
    {
        scanf("%d%d", &tip,&x);
        if(!tip)
            printf("%d\n", BSearch1(x));
        else
            if(tip==1)
                printf("%d\n", BSearch2(x));
            else
                printf("%d\n", BSearch3(x));
    }
    return 0;
}