#include <cstdio>

using namespace std;

const int nmx = 100002;
const int inf = 0x3f3f3f3f;

int n, v[nmx], m;

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

int cautare_binara(const int cond, const int nr) {
    static int st, dr, mij, pos;
    st = 1, dr = n, pos = -1;
    if(cond == 2)
        pos = inf;
    while(st <= dr) {
        mij = st + (dr - st) / 2;
        if(not cond) {
            if(v[mij] > nr)
                dr = mij - 1;
            else {
                if(v[mij] == nr)
                    pos = mij;
                st = mij + 1;
            }
            continue;
        }
        if(cond == 1) {
            if(v[mij] > nr)
                dr = mij - 1;
            else {
                if(mij > pos)
                    pos = mij;
                st = mij + 1;
            }
            continue;
        }
        if(v[mij] >= nr) {
            dr = mij - 1;
            if(mij < pos)
                pos = mij;
        } else
            st = mij + 1;
    }
    if(cond == 1 && pos == -1)
        return 0;
    return pos;
}

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

    citire();
    int cond, nr;
    for(int i = 1; i <= m; ++i) {
        scanf("%d %d", &cond, &nr);
        printf("%d\n", cautare_binara(cond,nr));
    }

    return 0;
}