#include <cstdio>

using namespace std;

int v[100005];

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

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

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

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

    int n, m, tip, val;
    scanf("%d", &n);

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

    scanf("%d", &m);

    for( ; m; -- m) {
        scanf("%d%d", &tip, &val);
        if(tip == 0)    printf("%d\n", bs0(1, n, val));
        else if(tip == 1)   printf("%d\n", bs1(1, n, val));
        else    printf("%d\n", bs2(1, n, val));
    }

    return 0;
}