#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n, q;
int v[100010];

void readAndSet() {
    fin >> n;

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

    fin >> q;
}

int solve0(int x) {
    int st = 1, dr = n;

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

        if (v[mij] <= x)
            st = mij + 1;
        else
            dr = mij;
    }

    if (v[st] == x)
        return st;
    if (st > 1 && v[st - 1] == x)
        return st - 1;
    return -1;
}

int solve1(int x) {
    int st = 1, dr = n;

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

        if (v[mij] <= x)
            st = mij + 1;
        else
            dr = mij;
    }

    if (v[st] <= x)
        return st;
    return st - 1;
}

int solve2(int x) {
    int st = 1, dr = n;

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

        if (v[mij] < x)
            st = mij + 1;
        else
            dr = mij;
    }

    return st;
}

void solveQueries() {
    while (q--) {
        int c, x;

        fin >> c >> x;

        if (c == 0)
            fout << solve0(x) << '\n';
        else if (c == 1)
            fout << solve1(x) << '\n';
        else
            fout << solve2(x) << '\n';
    }
}

int main() {
    readAndSet();
    solveQueries();
    return 0;
}