#include <bits/stdc++.h>
using namespace std;

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

int n, m, i, v[100005];
struct hh {
    int id, val;
} q[100005];

int cbin0(int val, int v[]) {
    int st = 1, dr = n, poz = -1;
    while (st <= dr) {
        int mid = (st + dr) / 2;

        if (v[mid] == val) poz = mid, st = mid + 1;
        else dr = mid - 1;
    }

    return poz;
}

int cbin1(int val, int v[]) {
    int st = 1, dr = n, poz = -1;
    while (st <= dr) {
        int mid = (st + dr) / 2;

        if (v[mid] <= val) poz = mid, st = mid + 1;
        else dr = mid - 1;
    }

    return poz;
}

int cbin2(int val, int v[]) {
    int st = 1, dr = n, poz = -1;
    while (st <= dr) {
        int mid = (st + dr) / 2;

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

    return poz;
}


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

    fin >> m;
    for (i = 1; i <= m; i++) fin >> q[i].id >> q[i].val;

    for (i = 1; i <= m; i++) {
        if (q[i].id == 0) fout << cbin0(q[i].val, v) << '\n';

        else if (q[i].id == 1) fout << cbin1(q[i].val, v) << '\n';

        else if (q[i].id == 2) fout << cbin2(q[i].val, v) << '\n';
    }

    return 0;
}