#include <stdio.h>

int i, n, v[100001], m, x, y;

int caut0(int p, int u, int key)
    //int mij;
    {
    int mij;
        while (p<=u) {
            mij = (p+u) / 2;
            if (v[mij]<=key) p=mij+1;
                     else u=mij-1;
        }
        mij=(p+u) / 2;
        if (v[mij]>key) mij=mij-1;
        if (v[mij]=key) return mij;
                 else return -1;
    }

int caut1(int p, int u, int key)
{
    int mij;
    while (p<u) {
        int mij=(p+u)/2;
        if (v[mij]<=key) p=mij+1;
        else u=mij;
    }
    mij=(p+u)/2;
    if (v[mij]>key) mij=mij-1;
    return mij;
}

int caut2(int p, int u, int key)
{
    int mij;
    while (p<u) {
        mij=(p+u)/2;
        if(v[mij]<key) p=mij+1;
        else u=mij;
    }
    mij=(p+u)/2;
    if (v[mij]<key) mij=mij+1;
    return mij;
}

int main()
{
    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);
    for (i=1;i<=m;i++){
        scanf("%d%d",&y,&x);
        if (y==0) printf("%d\n",caut0(1,n,x));
        if (y==1) printf("%d\n",caut1(1,n,x));
        if (y==2) printf("%d",caut2(1,n,x));
    }
    return 0;
}