#include <bits/stdc++.h>

#define MAXN 100001

using namespace std;

int N, M, A[MAXN];

int bsearch0(int val) {
    int left = 0, right = N - 1, middle, iterations = 50;

    while (iterations--) {
        middle = left + (right - left) / 2;
        if (A[middle] <= val) {
            left = middle;
        } else {
            right = middle;
        }
    }

    if (A[left] != val) return -2;
    return left;
}

int bsearch1(int val) {
    int left = 0, right = N - 1, middle, iterations = 50;

    while (iterations--) {
        middle = left + (right - left) / 2;
        if (A[middle] <= val) {
            left = middle;
        } else {
            right = middle;
        }
    }

    if (A[left] > val) return -2;
    return left;
}

int bsearch2(int val) {
    int left = 0, right = N - 1, middle, iterations = 50;

    while (iterations--) {
        middle = left + (right - left) / 2;
        if (A[middle] >= val) {
            right = middle;
        } else {
            left = middle;
        }
    }

    if (A[right] > val) return -2;
    return right;
}

int main() {
    int q, val;

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

    scanf("%d", &N);

    for (int it = 0; it < N; ++it) {
        scanf("%d", &A[it]);
    }

    scanf("%d", &M);

    for (int it = 0; it < M; ++it) {
        scanf("%d%d", &q, &val);
        if (q == 0) {
            printf("%d\n", bsearch0(val) + 1);
            continue;
        }
        if (q == 1) {
            printf("%d\n", bsearch1(val) + 1);
            continue;
        }
        if (q == 2) {
            printf("%d\n", bsearch2(val) + 1);
        }
    }

    return 0;
}