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

ifstream cin{"cautbin.in"};
ofstream cout{"cautbin.out"};

#define N_MAX 100005

int n, a[N_MAX];

int c_bin_0(int x) {
    int sol = -1;
    int stg = 1, drp = n;
    while (stg <= drp) {
        int mij = (stg + drp) / 2;

        if (a[mij] == x) {
            sol = mij;
            stg = mij + 1;
        } else if (a[mij] < x) {
            stg = mij + 1;
        } else {
            drp = mij - 1;
        }
    }

    return sol;
}

int c_bin_1(int x) {
    int sol = -1;
    int stg = 1, drp = n;
    while (stg <= drp) {
        int mij = (stg + drp) / 2;

        if (a[mij] <= x) {
            sol = mij;
            stg = mij + 1;
        } else {
            drp = mij - 1;
        }
    }

    return sol;
}

int c_bin_2(int x) {
    int sol = -1;
    int stg = 1, drp = n;
    while (stg <= drp) {
        int mij = (stg + drp) / 2;

        if (a[mij] >= x) {
            sol = mij;
            drp = mij - 1;
        } else {
            stg = mij + 1;
        }
    }

    return sol;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    int m;
    cin >> m;
    while (m--) {
        int tip, x;
        cin >> tip >> x;

        if (tip == 0)
            cout << c_bin_0(x);
        else if (tip == 1)
            cout << c_bin_1(x);
        else
            cout << c_bin_2(x);

        cout << '\n';
    }
}