#include <iostream>
#include <fstream>

using namespace std;

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

const int maxN = 1e5 + 5;

int v[maxN];

int lower_Bound (int val, int n) {
    int st = 1, dr = n, poz = -1;

    while(st <= dr) {
        int mij = (st + dr) / 2;

        if(val <= v[mij]) {
            dr = mij - 1;
            poz = mij;
        } else
            st = mij + 1;
    }
    return poz;
}

int upper_Bound (int val, int n, int op) {
    int st = 1, dr = n, poz = -1;

    while(st <= dr) {
        int mij = (st + dr) / 2;

        if(val >= v[mij]) {
            st = mij + 1;
            poz = mij;
        } else
            dr = mij - 1;
    }

    if(op == 1 && v[poz] != val)
        return -1;

    return poz;
}

int main()
{
    int n; fin >> n;

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

    int m; fin >> m;

    for(int i = 1; i <= m; ++i) {
        int op; fin >> op;
        int x; fin >> x;

        if(op == 0) {
            fout << upper_Bound(x, n, 1) << '\n';
        } else if(op == 1) {
            fout << upper_Bound(x, n, 2) << '\n';
        } else {
            fout << lower_Bound(x, n)  << '\n';
        }
    }

    return 0;
}