#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 solve0(vector <int>&v, int x) {
    int left = 0, right = v.size() - 1;
    while(right - left > 1) {
        int mid = left + (right - left) / 2;
        if (v[mid] < x) {
            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);
    for (int i = 0; i < N; ++i) {
        cin >> v[i];
    }
    int Q; cin >> Q;
    while(Q--) {
        int type, x;
        cin >> type >> x;
        int answer = 0;

        if (type == 0) {
            //search for the biggest position p s.t. v[p] == x if not output -1
            answer = solve0(v, x + 1);
            answer -= 1;
            if (answer < 0 || v[answer] != x) {
                cout << -1 << "\n";
            } else {
                cout << answer + 1 << "\n";
            }

        } else if (type == 1) {
            //max(p) s.t. v[p] <= x
            answer = solve0(v, x + 1);
            if (v[answer] > x) {
                answer--;
            }
            cout << answer + 1<< "\n";
        } else if (type == 2) {
            //min(p) s.t. v[p] >= x
            answer = solve0(v, x - 1);
            if (v[answer] < x && answer + 1 < v.size()) {
                answer += 1;
            }
            cout << answer + 1 << "\n";
        }
    }

    return 0;
}