#include <cstdio>

using namespace std;

int n, m, v[100005], quest, x;

int solve_quest0(int x)
{
    int step, poz;

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

    for (poz = 0; step; step >>= 1)
        if (poz + step <= n && v[poz + step] == x)
            poz += step;

    if (!poz) poz = -1;

    return poz;
}

int solve_quest1(int x)
{
    int step, poz;

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

    for (poz = 0; step; step >>= 1)
        if (poz + step <= n && v[poz + step] <= x)
            poz += step;

    return poz;
}

int solve_quest2(int x)
{
    int step, poz;

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

    for (poz = n; step; step >>= 1)
        if (poz - step >= 1 && v[poz - step] >= x)
            poz -= step;

    return poz;
}

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

    scanf("%d", &n);

    for (int i = 1; i <= n; ++i) scanf("%d", &v[i]);

    scanf("%d", &m);

    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &quest, &x);
        if (!quest) printf("%d\n", solve_quest0(x));
        else if (quest == 1) printf("%d\n", solve_quest1(x));
             else printf("%d\n", solve_quest2(x));
    }

    fclose(in);
    fclose(out);
    return 0;
}