#include <stdio.h>

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

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

static int cb0(unsigned long x)
{
    int l, r, m;

    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 unsigned cb1(unsigned long x)
{
    int 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;
    return m;
}

static unsigned cb2(unsigned long x)
{
    int 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;
    return m;
}

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

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

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

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

    return 0;
}