#include <cstdio>

using namespace std;

#define Nmax 100001

int N, M;
int v[Nmax];

void citire(){

    freopen("cautbin.in", "rt", stdin);

    scanf("%d", &N);

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

int cauta0(int x){

    int st = 1, dr = N, m;

    while ( st <= dr ) {

        m = st + ( ( dr - st ) >> 1 );

        if ( v[m] <= x )
            st = m + 1;
        else
            dr = m - 1;
    }

    if ( v[m] > x )
        m--;

    if ( v[m] == x )
        return m;

    return -1;
}

int cauta1(int x){

    int st = 1, dr = N, m;

    while ( st < dr ){

        m = st + ( ( dr - st ) >> 1 );

        if ( v[m] <= x )
            st = m + 1;
        else
            dr = m;
    }

    m = st + ( ( dr - st ) >> 1 );

    if ( v[m] > x )
        m--;

    return m;
}

int cauta2(int x){

    int st = 1, dr = N, m;

    while ( st < dr ){

        m = st + ( ( dr - st ) >> 1 );

        if ( v[m] <= x )
            st = m + 1;
        else
            dr = m;
    }

    m = st + ( ( dr - st ) >> 1 );

    if ( v[m] < x )
        m++;

    return m;
}

void rezolva(){

    freopen("cautbin.out", "wt", stdout);

    scanf("%d", &M);

    int tip, x;

    for(; M; M--){

        scanf("%d %d", &tip, &x);

        switch(tip){

            case 0: printf("%d\n", cauta0(x));   break;
            case 1: printf("%d\n", cauta1(x));   break;
            case 2: printf("%d\n", cauta2(x));   break;

            default:    break;
        }
    }
}


int main(){

    citire();
    rezolva();

    return 0;
}