#include <fstream>

using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int n, m, a[100005], x, y, z;

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

}

int caz1(int h) {
    int dr = n, st = 1, poz = -1;
    while (st <= dr) {
        m = (dr + st) / 2;
        if (a[m] > h)dr = m - 1;
        else {
            if (a[m] == h)poz = m;
            st = m + 1;
        }
        if (a[st] > h)break;
    }
    return poz;
}

int caz2(int h) {
    int dr = n, st = 1, poz = -1;
    while (st <= dr) {
        m = (dr + st) / 2;
        if (a[m] > h)dr = m - 1;
        else {
            if (a[m] <= h)poz = m;
            st = m + 1;
        }
    }
    return poz;
}

int caz3(int h) {
    int dr = n, st = 1, poz = -1;
    while (st <= dr) {
        m = (dr + st) / 2;
        if (a[m] >= h) {
            if (a[m] >= h)poz = m;
            dr = m - 1;
        } else { st = m + 1; }
    }
    return poz;
}

void afisare() {
    int i = 0;
    for (i = 1; i <= m; i++) {
        cin >> y >> z;
        if (y == 0)cout << caz1(z);
        else if (y == 1)cout << caz2(z);
        else cout << caz3(z);
        cout << endl;
    }
}

int main() {
    citire();
    afisare();
    return 0;
}