#include <fstream>
#include <algorithm>
using namespace std;

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

#define NMAX 100001

int v[NMAX], n, i, m, x, tip;

int cbMPpoz(int x) {
    int i, step, poz = -1;
    for(step = 1; step <= n; step = (step << 1));

    for(i = 0; step != 0; step = (step >> 1))
        if(i + step <= n && v[i + step] <= x) {
            if(v[i + step] == x)
                poz = i + step;
            i += step;
        }
    return poz;
}

int cbMPdr(int x) {
    int i, step;
    for(step = 1; step < n ; step = (step << 1));

    for(i = 0; step != 0; step = (step >> 1))
        if(i + step <= n && v[i + step] <= x)
            i += step;

    return i;
}

int cbMPst(int x) {
    int i, step, poz;
    for(step = 1; step < n; step <<= 1);

    for(i = 0; step != 0; step >>= 1)
        if(i + step <= n && v[i + step] >= x)
            poz = step;
    return poz;
}

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

    cin >> m;
    for(i = 1; i <= m; i++) {
        cin >> tip >> x;
        if(tip == 0)
            cout << cbMPpoz(x);
        else if(tip == 1)
                cout << cbMPdr(x);
        else cout << cbMPst(x);
        cout << '\n';
    }

    return 0;
}