#include<iostream>

using namespace std;

int A[100010], x, n, m, op, result;

int findHighestIdx (int A[], int x, int n) {
    int start = 0;
    int end = n - 1;
    int p = -1;
    while (start <= end) {
        int mid = (start + end) / 2;
        if (A[mid] == x) {
            p = mid;
            start = mid + 1;
        }
        else if (A[mid] > x) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return p;
}

int maxIdx (int A[], int x, int n) {
    int start = 0;
    int end = n - 1;
    int p = -1;
    while (start <= end) {
        int mid = (start + end) / 2;
        if (A[mid] <= x) {
            p = mid;
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return p;
}

int minIdx (int A[], int x, int n) {
    int start = 0;
    int end = n - 1;
    int p = -1;
    while (start <= end) {
        int mid = (start + end) / 2;
        if (A[mid] >= x) {
            p = mid;
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return p;
}


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

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >>A[i];
    }
    cin >> m;

    for (int j = 0; j < m; j++) {
        cin >> op >> x;
        if (op == 0) {
            result = findHighestIdx(A, x, n);
        } else if (op == 1) {
            result = maxIdx(A, x, n);
        } else {
            result = minIdx(A, x, n);
        }
        cout << result + (result != -1 ) << endl;
    }
    return 0;
}