#include <cstdio>

using namespace std;

const int NMAX = 100001;
int v[NMAX];

int bin(int st, int dr, int val) {
    int med, last = -1;
    while(st <= dr) {
        med = st + (dr - st) / 2;
        if(v[med] <= val) {
            if(v[med] == val)
                last = med;
            st = med + 1;
        } else {
            dr = med - 1;
        }
    }
    return last;
}

int bin1(int st, int dr, int val) {
    int med, last = -1;
    while(st <= dr) {
        med = st + (dr - st) / 2;
        if(v[med] <= val) {
            last = med;
            st = med + 1;
        } else {
            dr = med - 1;
        }
    }
    return last;
}

int bin2(int st, int dr, int val) {
    int med, last = -1;
    while(st <= dr) {
        med = st + (dr - st) / 2;
        if(v[med] >= val) {
            last = med;
            dr = med - 1;
        } else {
            st = med + 1;
        }
    }
    return last;
}

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

    int n, m, a, b;
    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", &a, &b);
        if(a == 0) {
            printf("%d\n", bin(1, n, b));
        } else
        if(a == 1) {
            printf("%d\n", bin1(1, n, b));
        } else {
            printf("%d\n", bin2(1, n, b));
        }
    }

    return 0;
}