#include <bits/stdc++.h>
using namespace std;

int cauta_ultima_aparitie(const vector<int>& v, int x) {
    int st = 0, dr = v.size() - 1, poz = -1;
    while (st <= dr) {
        int mid = st + (dr - st) / 2;
        if (v[mid] == x) {
            poz = mid;
            st = mid + 1;
        } else if (v[mid] < x) {
            st = mid + 1;
        } else {
            dr = mid - 1;
        }
    }
    return poz;
}

int cea_mai_mare_pozitie(const vector<int>& v, int x) {
    int st = 0, dr = v.size() - 1, poz = -1;
    while (st <= dr) {
        int mid = st + (dr - st) / 2;
        if (v[mid] <= x) {
            poz = mid;
            st = mid + 1;
        } else {
            dr = mid - 1;
        }
    }
    return poz;
}

int cea_mai_mica_pozitie(const vector<int>& v, int x) {
    int st = 0, dr = v.size() - 1, poz = -1;
    while (st <= dr) {
        int mid = st + (dr - st) / 2;
        if (v[mid] >= x) {
            poz = mid;
            dr = mid - 1;
        } else {
            st = mid + 1;
        }
    }
    return poz;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);

    int N;
    cin >> N;
    vector<int> sir(N);
    for (int i = 0; i < N; i++) {
        cin >> sir[i];
    }

    int M;
    cin >> M;

    for (int i = 0; i < M; i++) {
        int tip, x;
        cin >> tip >> x;
        if (tip == 0) {
            cout << cauta_ultima_aparitie(sir, x) << '\n';
        } else if (tip == 1) {
            cout << cea_mai_mare_pozitie(sir, x) << '\n';
        } else {
            cout << cea_mai_mica_pozitie(sir, x) << '\n';
        }
    }

    return 0;
}