#include <fstream>

using namespace std;

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

int n, m, v[100001];

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

    fin >> m;
    for (int i = 1; i <= m; i++) {
        int q, x;
        fin >> q >> x;
        if (q == 0) {
            unsigned int st = 1, dr = n, mid;
            while (st < dr) {
                mid = (st + dr) / 2;
                if (v[mid] <= x)
                    st = mid + 1;
                else
                    dr = mid;
            }
            mid = (st + dr) / 2;
            if (v[mid] > x)
                mid--;
            if (v[mid] == x) {
                fout << mid << "\n";
                continue;
            }
            fout << "-1\n";
        }
        if (q == 1) {
            unsigned int st = 1, dr = n, mid;
            while (st < dr) {
                mid = (st + dr) / 2;
                if (v[mid] <= x)
                    st = mid + 1;
                else
                    dr = mid;
            }
            mid = (st + dr) / 2;
            if (v[mid] > x) {
                mid--;
            }
            fout << mid << "\n";
        }
        if (q == 2) {
            unsigned int st = 1, dr = n, mid;
            while (st < dr) {
                mid = (st + dr) / 2;
                if (v[mid] < x)
                    st = mid + 1;
                else
                    dr = mid;
            }
            mid = (st + dr) / 2;
            if (v[mid] < x) {
                mid++;
            }
            fout << mid << "\n";
        }
    }

    return 0;
}