#include <fstream>
#include <vector>
using namespace std;

const int DIM = 1e5 + 1; // 1ex = 10^x

int n;
int a[DIM];

int lowerbound(int val) {
    int st = 1, dr = n;
    while (st <= dr) {
        int mij = (st + dr) / 2;
        if (val < a[mij])
            dr = mij - 1;
        else if (a[mij] <= val)
            st = mij + 1;
    }

    return dr;
}

int upperbound(int val) {
    int st = 1, dr = n;
    while (st <= dr) {
        int mij = (st + dr) / 2;
        if (val <= a[mij])
            dr = mij - 1;
        else if (a[mij] < val)
            st = mij + 1;
    }

    return st;
}

int main() {
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");

    fin >> n;
    for (int i = 1; i <= n ; ++i)
        fin >> a[i];

    int q;
    fin >> q;

    for (int i = 1; i <= q ; ++i) {
        int type, val;
        fin >> type >> val;

        if (type == 0) {
            int pos = lowerbound(val);
            if (a[pos] != val)
                pos = -1;
            fout << pos << endl;
        } else if (type == 1) {
            int pos = lowerbound(val);
            fout << pos << endl;
        } else if (type == 2) {
            int pos = upperbound(val);
            fout << pos << endl;
        }
    }

    return 0;
}