#include <fstream>

using namespace std;

//ifstream cin ("input"); ofstream cout ("output");
ifstream cin ("cautbin.in"); ofstream cout ("cautbin.out");

/*
X:         1 3 3 3 5
POZITII:   1 2 3 4 5

CAUTARE BINARA 0 PENTRU VAL 3:
st = 1
dr = 5
mij = 3
raspuns = 3

st = 4
dr = 5
mij = 4
raspuns = 4

st = 5
dr = 5
mij = 5

st = 5
dr = 4
END WHILE

---------------------------------
CAUTARE BINARA 1 PENTRU VAL 4:
st = 1
dr = 5
mij = 3
raspuns = 3

st = 4
dr = 5
mij = 4
raspuns = 4

st = 5
dr = 5
mij = 5

st = 5
dr = 4
END WHILE
*/


int n;
int x[100001];

int cautareBinara0(int val){
    int st = 1;
    int dr = n;
    int raspuns = -1;

    while (st <= dr){
        int mij = (st + dr) / 2;
        if (x[mij] <= val){
            if (x[mij] == val){
                raspuns = mij;
            }
            st = mij + 1;
        }
        else{
            dr = mij - 1;
        }
    }

    return raspuns;
}

int cautareBinara1(int val){
    int st = 1;
    int dr = n;
    int raspuns = -1;

    while (st <= dr){
        int mij = (st + dr) / 2;
        if (x[mij] <= val){
            raspuns = mij;
            st = mij + 1;
        }
        else{
            dr = mij - 1;
        }
    }

    return raspuns;
}

int cautareBinara2(int val){
    int st = 1;
    int dr = n;
    int raspuns = -1;

    while (st <= dr){
        int mij = (st + dr) / 2;
        if (x[mij] < val){
            st = mij + 1;
        }
        else{
            raspuns = mij;
            dr = mij - 1;
        }
    }

    return raspuns;
}


int main() {

    //freopen("input", "r", stdin); freopen("output", "w", stdout); //daca vrei sa fie din consola comenteaza linia de jos

    cin>>n;
    for (int i=1; i<=n; i++){
        cin>>x[i];
    }

    int m;
    cin>>m;

    while (m--){
        int tip, val;
        cin>>tip>>val;

        if (tip == 0){
            cout<<cautareBinara0(val)<<'\n';
        }
        if (tip == 1){
            cout<<cautareBinara1(val)<<'\n';
        }
        if (tip == 2){
            cout<<cautareBinara2(val)<<'\n';
        }
    }

    return 0;
}