#include <stdio.h>

static int v[100000];

static int cb(int x, int n, int op)
{
    int mid, pos;

    for (mid = 1; mid < n; mid <<= 1)
        ;

    for (pos = op == 2 ? n - 1 : 0; mid; mid >>= 1) {
        if (op == 2) {
            if (pos - mid >= 0 && v[pos - mid] >= x) {
                pos -= mid;
            }
        } else {
            if (pos + mid < n && v[pos + mid] <= x) {
                pos += mid;
            }
        }
    }

    return pos;
}

int main(void)
{
    int n, m, i, op, x, r;

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

    for (scanf("%d", &n), i = 0; i < n; i++) {
        scanf("%d", &v[i]);
    }

    for (scanf("%d", &m); m; m--) {
        scanf("%d %d", &op, &x);
        r = cb(x, n, op);
        printf("%d\n", (op || v[r] == x) * (r + 1) + !(op || v[r] == x) * -1);
    }

    return 0;
}