#include <cstdio>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <string>
#include <set>
#include <stack>
#define pb push_back

#define mp make_pair
#define f first
#define s second
#define ll long long

using namespace std;

int solve(vector <int>& v, int x) {
    int left = 1, right = v.size() - 1;
    while(right - left > 1) {
        int mid = left + (right - left) / 2;
        if (x > v[mid]) {
            left = mid;
        } else {
            right = mid;
        }
    }
    return right;
}
int main() {
#ifndef ONLINE_JUDGE
    ifstream cin("cautbin.in");
    ofstream cout("cautbin.out");
#endif

    int N; cin >> N;
    vector <int> v(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> v[i];
    }
    v[0] = -1;
    int Q; cin >> Q;
    while(Q--) {
        int type, x;
        cin >> type >> x;
        int pos = 0;
        if (type == 0) {
            pos = solve(v, x + 1);
            if (v[pos] != x) {
                pos--;
            }
            if (v[pos] != x) {
                cout << -1 << "\n";
            } else {
                cout << pos << "\n";
            }
        } else if(type == 1) {
            pos = solve(v, x + 1);
            if (v[pos] > x) {
                pos--;
            }
            cout << pos << "\n";
        } else if(type == 2) {
            pos = solve(v, x);
            if (pos > 0 && v[pos - 1] >= x) {
                pos--;
            }

            cout << pos << "\n";
        }
    }
    return 0;
}