#include <stdio.h>
#include <stdlib.h>
int v[100001];

int cautare0 (int st, int dr, int el) {
    int mij;

    while (st <= dr) {
        mij = (st + dr) / 2;
        if (v[mij] <= el)
            st = mij + 1;
        else
            dr = mij - 1;
    }

    mij= (st + dr) / 2;

    if (v[mij] > el)
        mij --;
    if (v[mij] == el)
        return mij;
    return -1;
}

int cautare1 (int st, int dr, int el) {
    int mij;

    while (st < dr) {
        mij = (st + dr) / 2;
        if (v[mij] <= el)
            st = mij + 1;
        else
            dr = mij;
    }

    mij= (st + dr) / 2;

    if (v[mij] > el)
        mij--;
        return mij;
}

int cautare2 (int st, int dr, int el) {
    int mij;

    while (st < dr) {
        mij = (st + dr) / 2;
        if (v[mij] < el)
            st = mij + 1;
        else
            dr = mij;
    }

    mij= (st + dr) / 2;

     if (v[mij] < el)
        mij++;
        return mij;
}
int main()
{   int n,m,i,x,y;

    scanf("%d",&n);

    for(i=1;i<=n;i++){
        scanf("%d",&v[i]);
    }

    scanf("%d",&m);

    while(m){
            scanf("%d%d",&x,&y);
            if(x==0)
                printf("%d\n",cautare0(1,n,y));
            if(x==1)
                printf("%d\n",cautare1(1,n,y));
            if(x==2)
                printf("%d\n",cautare2(1,n,y));
        m--;
    }

    return 0;
}