#include <fstream>
#include <algorithm>

using namespace std;

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

#define NMAX 100001

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

int cautBinarSt(int x) {
    int st = 1, dr = n;
    while(st <= dr) {
        int mid = (st + dr) / 2;
        if(x <= v[mid])
            dr = mid - 1;
        else st = mid + 1;
    }
    return st;
}

int cautBinarDr(int x) {
    int st = 1, dr = n;
    while(st <= dr) {
        int mid = (st + dr) / 2;
        if(x < v[mid])
            dr = mid - 1;
        else st = mid + 1;
    }
    return dr;
}

int cautBinar(int x) {
    int st = 1, dr = n, poz = -1;
    while(st <= dr) {
        int mid = (st + dr) / 2;
        if(x < v[mid])
            dr = mid - 1;
        else {
            if(x == v[mid])
                poz = mid;
            st = mid + 1;
        }
    }
    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 << cautBinar(x);
        else if(tip == 1)
            cout << cautBinarDr(x);
        else cout << cautBinarSt(x);
        cout << '\n';
    }

    return 0;
}