#include <stdio.h>

#define IN "cautbin.in"
#define OUT "cautbin.out"
#define NMAX 100000

static unsigned long A[NMAX + 1], n;

static unsigned long cautbin(unsigned long x)
{
    unsigned long l, r, m = 0;

    l = 1;
    r = n;
    while (l < r) {
        m = l + ((r - l) >> 1);
        if (A[m] < x)
            l = m + 1;
        else if (A[m] > x)
            r = m - 1;
        else
            return m;
    }

    return m;
}

int main(void)
{
    unsigned long i, m, r, x, o;

    freopen(IN, "r", stdin);
    freopen(OUT, "w", stdout);

    scanf("%lu", &n);
    for (i = 1; i <= n; i++)
        scanf("%lu", &A[i]);

    scanf("%lu", &m);
    while (m--) {
        scanf("%lu %lu", &o, &x);
        r = cautbin(x);
        if (o == 0) {
            while (A[r + 1] == x)
                r++;
            printf("%ld\n", A[r] == x ? r : -1);
        } else if (o == 1) {
            while (A[r + 1] <= x)
                ++r;
            printf("%lu\n", r);
        } else {
            while (A[r - 1] >= x)
                --r;
            printf("%lu\n", r);
        }
    }

    return 0;
}