#include <iostream>
#include <fstream>

using namespace std;

int caut(int v[], int n, int x, int op) {
    int st = 1, dr = n, m, ok = -1;
    while (st <= dr) {
        m = (st + dr) / 2;
        if (x == v[m]) ok = m;
        if (x > v[m])st = m + 1;
        else dr = m - 1;
    }
    if (op == 0) {
        if (ok == -1)
            return -1;
        while (v[m] == x)
            m++;
        return m - 1;
    } else if (op == 1) {
        if(ok == -1)
            return dr;
        while (v[m] == x)
            m++;
        return m - 1;
    } else {
        if(ok == -1)
            return st;
        while (v[m] == x)
            m--;
        return m + 1;
    }
}

int main() {
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    int v[100001], n, m, i, instr, x;
    fin >> n;
    for (i = 1; i <= n; ++i)
        fin >> v[i];
    fin >> m;
    for (i = 1; i <= m; ++i) {
        fin >> instr >> x;
        fout << caut(v, n, x, instr) << "\n";
    }
}