#include <stdio.h>

#define IN "cautbin.in"
#define OUT "cautbin.out"
#define N 100001
#define NF -1

static unsigned long v[N], n;

static long cautbin_0(long);
static long cautbin_1(long);
static long cautbin_2(long);

int main(void) {

    long i, m, x;
    int q;

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

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

    (void) scanf("%ld", &m);

    while(m--) {

        (void) scanf("%d %ld", &q, &x);

        switch(q) {

            case 0:
            printf("%ld\n", cautbin_0(x));
            break;

            case 1:
            printf("%ld\n", cautbin_1(x));
            break;

            case 2:
            printf("%ld\n", cautbin_2(x));
            break;
        }
    }

    return 0;
}

long cautbin_0(long x) {

    long st = 0, dr = n, mid;

    do {

        mid = st + (dr - st) / 2;

        if(x < v[mid]) dr = mid - 1;
        else st = mid + 1;
    } while(v[mid] != x && st <= dr);

    if(v[mid] != x) return NF;
    else while(v[mid + 1] == x) ++mid;

    return mid;
}

long cautbin_1(long x) {

    long st = 0, dr = n, mid;

    do {

        mid = st + (dr - st) / 2;

        if(x < v[mid]) dr = mid - 1;
        else st = mid + 1;
    } while(v[mid] != x && st <= dr);

    while(v[mid + 1] <= x) ++mid;

    return mid;
}

long cautbin_2(long x) {

    long st = 0, dr = n, mid;

    do {

        mid = st + (dr - st) / 2;

        if(x < v[mid]) dr = mid - 1;
        else st = mid + 1;
    } while(v[mid] != x && st <= dr);

    while(v[mid -1] >= x) --mid;

    return mid;
}