#include <fstream>
using namespace std;

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

int n, T, v[100005], i, q, nr;

int cautbin0(int x) {
    int st = 1, dr = n, m, sol = -1;
    while(st <= dr) {
        m = (st + dr) / 2;
        if(v[m] == x) {
            sol = m;
            st = m+1;
        }
        else if (x < v[m])
            dr = m - 1;
        else
            st = m + 1;
    }
    return sol;
}

int cautbin1(int x) {
    int st = 1, dr = n, m, sol = -1;
    while(st <= dr) {
        m = (st + dr) / 2;
        if(v[m] == x) {
            sol = m;
            st = m+1;
        }
        else if (x < v[m])
            dr = m - 1;
        else
            st = m + 1;
    }
    return sol;
}

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

int main() {
    fin >> n;
    for(i = 1; i <= n; ++i)
        fin >> v[i];
    fin >> T;
    for(i = 1; i <= T; ++i) {
        fin >> q >> nr;
        if(q == 0)
            fout << cautbin0(nr);
        else if (q == 1)
            fout << cautbin1(nr);
        else
            fout << cautbin2(nr);
        fout << '\n';
    }
}