#include <fstream>
#include <vector>

using namespace std;

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

int N, M;
vector<int> v;

int binary_search_0(int x) {
    int st = 0, dr = N - 1, ans = -1;
    while (st <= dr) {
        int mid = st + (dr - st) / 2;
        if (v[mid] == x) {
            ans = mid;     // candidatul curent
            st = mid + 1;  // caut mai la dreapta
        } else if (v[mid] < x) {
            st = mid + 1;
        } else {
            dr = mid - 1;
        }
    }
    return (ans == -1 ? -1 : ans + 1); // transformare la 1-based
}

int binary_search_1(int x) {
    int st = 0, dr = N - 1, ans = -1;
    while (st <= dr) {
        int mid = st + (dr - st) / 2;
        if (v[mid] <= x) {
            ans = mid;
            st = mid + 1;
        } else {
            dr = mid - 1;
        }
    }
    return ans + 1;
}

int binary_search_2(int x) {
    int st = 0, dr = N - 1, ans = -1;
    while (st <= dr) {
        int mid = st + (dr - st) / 2;
        if (v[mid] >= x) {
            ans = mid;
            dr = mid - 1;
        } else {
            st = mid + 1;
        }
    }
    return ans + 1;
}

int main() {
    fin >> N;
    v.resize(N);
    for (int i = 0; i < N; ++i) {
        fin >> v[i];
    }

    fin >> M;
    for (int i = 0; i < M; ++i) {
        int tip, x;
        fin >> tip >> x;
        if (tip == 0) {
            fout << binary_search_0(x) << "\n";
        } else if (tip == 1) {
            fout << binary_search_1(x) << "\n";
        } else {
            fout << binary_search_2(x) << "\n";
        }
    }

    return 0;
}