#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

int v[200001], n, i, st, dr, mij, x, m, tip;

int main() {
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdin);
    //1 2 7 9 11 13
    // <= v[mij]   > v[mij]
    //[st, mij] [mij+1, dr]
    //
    //X=11 -> 5
    cin >> n;
    for(i = 1; i <= n; i ++) {
        cin >> v[i];
    }
    cin >> m;
    for(i = 1; i <= m; i ++) {
        cin >> tip >> x;
        if(tip == 2) {
            st = 1;
            dr = n;
            while (st < dr) {
                mij = (st + dr) / 2;
                if (x <= v[mij]) // mergem in partea stanga
                    dr = mij;
                else // mergem in partea dreapta
                    st = mij + 1;
            }
            cout << st << '\n';
        } else if(tip == 1) {
            st = 1;
            dr = n;
            while (st < dr) {
                mij = (st + dr) / 2;
                if (x+1 <= v[mij]) // mergem in partea stanga
                    dr = mij;
                else // mergem in partea dreapta
                    st = mij + 1;
            }
            if(x >= v[n])
                cout << n << '\n';
            else
                cout << st-1 << '\n';
        } else {
            st = 1;
            dr = n;
            while (st < dr) {
                mij = (st + dr) / 2;
                if (x+1 <= v[mij]) // mergem in partea stanga
                    dr = mij;
                else // mergem in partea dreapta
                    st = mij + 1;
            }
            int raspuns;
            if(x >= v[n])
                raspuns = n;
            else
                raspuns = st - 1;
            if(v[raspuns] != x)
                cout << "-1\n";
            else
                cout << raspuns << '\n';
        }
    }

    return 0;
}