#include <bits/stdc++.h>
#define MOD 1999999973

using namespace std;

int binsearch1(vector <int> &v, int x) {
    int step = 1, n = v.size(), ans = 0;
    for (; step < n; step <<= 1) {}
    for (; step; step >>= 1)
        if (ans + step < n && v[ans + step] <= x)
            ans += step;

    return ans;
}

int binsearch0(vector <int> &v, int x) {
    int pos = binsearch1(v, x);
    return (v[pos] == x ? pos : -1);
}

int binsearch2(vector <int> &v, int x) {
    int step = 1, n = v.size(), ans = v.size() - 1;
    for (; step < n; step <<= 1) {}
    for (; step; step >>= 1)
        if (ans - step >= 0 && v[ans - step] >= x)
            ans -= step;

    return ans;
}

void solve() {
    int n, q, type, x;
    cin >> n;

    vector <int> v(n);
    for (int &x : v)
        cin >> x;

    int (*binsearch[])(vector <int> &, int) = {binsearch0, binsearch1, binsearch2};

    cin >> q;
    while (q--) {
        cin >> type >> x;
        cout << (*binsearch[type])(v, x) + 1 << '\n';
    }
}

int main() {

    // #ifndef ONLINE_JUDGE
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    // #endif

    int t = 1;
    // cin >> t;

    while (t--)
        solve();

    return 0;
}