#include <cstdio>
#include <vector>
#include <cstdlib>

using namespace std;

void read(int &n, int &m, vector<int> &arr, vector<pair<int, int> > &queries) {
    int arr_val;
    int query_type, query_val;

    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%d", &arr_val);
        arr.push_back(arr_val);
    }

    scanf("%d", &m);

    for (int i = 0; i < m; i++) {
        scanf("%d %d", &query_type, &query_val);
        queries.push_back(make_pair(query_type, query_val));
    }
}

int bin_search(vector<int> arr, int target_val) {
    int lo, hi;
    int mid;

    lo = 0;
    hi = arr.size() - 1;

    while (lo <= hi) {
        mid = (lo + hi) / 2;

        if (arr[mid] == target_val) {
            return mid;
        }
        if (arr[mid] < target_val) {
            lo = mid + 1;
        } else if (arr[mid] > target_val) {
            hi = mid - 1;
        }
    }

    return -mid;
}

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

    int n, m;
    vector<int> arr;
    vector<pair<int, int> > queries;

    read(n, m, arr, queries);

    for (vector<pair<int, int> >:: iterator it = queries.begin(); it != queries.end(); it++) {
        int index = bin_search(arr, it->second);
        int output;

        switch (it->first) {
        case 0:
            if (index < 0) {
                output = -1;
            } else {
                output = index;
                while (arr[output] == arr[index]) {
                    output++;
                }
                output--;
            }
            break;
        case 1:
            index = abs(index);
            output = index;
            while (arr[output] == arr[index]) {
                output++;
            }
            output--;
            while (arr[output] > arr[index]) {
                output--;
            }
            break;
        default:
            index = abs(index);
            output = index;
            while (arr[output] == arr[index]) {
                output--;
            }
            output++;
            while (arr[output] < arr[index]) {
                output++;
            }
            break;
        }

        printf("%d\n", output + 1);
    }
}