#include <bits/stdc++.h>
#define MAXN 100000

using namespace std;

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

int n, arr[MAXN], m;
void citire() {
    fin >> n;
    for (int i = 0; i < n; i++)
        fin >> arr[i];
    fin >> m;
}

int cb1(int x) {
    int lo = 0, hi = n - 1, pos = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == x)
            pos = mid + 1;
        if (arr[mid] <= x)
            lo = mid + 1;
        else
            hi = mid - 1;
    }
    return pos;
}

int cb2(int x) {
    int lo = 0, hi = n - 1, pos;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] <= x)
            pos = mid + 1, lo = mid + 1;
        else
            hi = mid - 1;
    }
    return pos;
}

int cb3(int x) {
    int lo = 1, hi = n - 1, pos;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] >= x)
            pos = mid + 1, hi = mid - 1;
        else
            lo = mid + 1;
    }
    return pos;
}

int rezolvare() {
    int t, x;
    fin >> t >> x;
    switch (t) {
        case 0:
            fout << cb1(x) << '\n';
            break;
        case 1:
            fout << cb2(x) << '\n';
            break;
        case 2:
            fout << cb3(x) << '\n';
            break;
    }
}

int main() {
    citire();
    for (int i = 0; i < m; i++)
        rezolvare();
    return 0;
}