#include <stdio.h>

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

static long A[NMAX + 1], n;

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

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

    while (A[m + 1] == x)
        ++m;
    return A[m] == x ? m : -1;
}

static long cb1(long x)
{
    long l, r, m;

    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;
    }
    m = l + ((r - l) >> 1);

    if (A[m] > x && m > 0)
        --m;
    return m;
}

static long cb2(long x)
{
    long l, r, m;

    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;
    }
    m = l + ((r - l) >> 1);

    if (A[m] < x && m < n)
        ++m;
    return m;
}

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

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

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

    scanf("%ld", &m);
    while (m--) {
        scanf("%ld %ld", &o, &x);
        if (o == 0)
            printf("%ld\n", cb0(x));
        if (o == 1)
            printf("%ld\n", cb1(x));
        if (o == 2)
            printf("%ld\n", cb2(x));
    }

    return 0;
}