#include<iostream>
#include<cstdio>

using namespace std;

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

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

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


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

    // cin >> n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
         scanf("%d", &A[i]);
        // cin >>A[i];
    }
    // cin >> m;
     scanf("%d", &m);

    for (int j = 0; j < m; j++) {
         scanf("%d %d", &op, &x);
        // cin >> op >> x;
        if (op == 0) {
            result = findHighestIdx(x, n);
        } else if (op == 1) {
            result = maxIdx(x, n);
        } else {
            result = minIdx(x, n);
        }
        printf("%d\n",result + (result != -1 ));
        // cout << result + (result != -1 ) << endl;
    }
    return 0;
}