#include <fstream>

using namespace std;

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

const int NMAX = 1e5;

int v[NMAX];

int bin_search1(int x, int n, int type) {

    int st = 0, dr = n - 1, mid = 0, pos = -1;
    while (st <= dr) {

        mid = ((st + dr) >> 1);
        if (v[mid] <= x) {
            st = mid + 1;
            pos = mid;
        } else {
            dr = mid - 1;
        }
    }

    if (type == 0 && v[pos] != x) {
        return -2;
    }

    return pos;
}

int bin_search2(int x, int n) {

    if (x > v[n - 1]) {
        return n - 1;
    }

    int st = 0, dr = n - 1, mid = 0, pos = -1;
    while (st <= dr) {

        mid = ((st + dr) >> 1);
        if (v[mid] >= x) {
            dr = mid - 1;
            pos = mid;
        } else {
            st = mid + 1;
        }
    }

    return pos;
}

int main() {

    int n = 0;
    fin >> n;

    for (int i = 0; i < n; i++) {
        fin >> v[i];
    }

    int q = 0;
    fin >> q;

    int type = 0, x = 0;
    for (int i = 0; i < q; i++) {
        fin >> type >> x;
        if (type == 0 || type == 1) {
            fout << bin_search1(x, n, type) + 1 << "\n";
        } else {
            fout << bin_search2(x, n) + 1 << "\n";
        }
    }

    return 0;
}