#include <bits/stdc++.h>

using namespace std;

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

int main() {
    int n, m, v[100001], x, c;

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

    fin >> m;
    while (m--) {
        fin >> c >> x;

        if (c == 0) {
            int idx = -1;
            int st = 1, dr = n;

            while (st <= dr) {
                int mid = st + (dr - st) / 2;

                if (v[mid] == x) {
                    idx = mid;
                    st = mid + 1;
                } else if (v[mid] < x)
                    st = mid + 1;
                else if (v[mid] > x)
                    dr = mid - 1;
            }
            fout << idx << '\n';
        } else if (c == 1) {
            int idx = -1;
            int st = 1, dr = n;

            while (st <= dr) {
                int mid = st + (dr - st) / 2;

                if (v[mid] <= x) {
                    idx = mid;
                    st = mid + 1;
                } else
                    dr = mid - 1;
            }
            fout << idx << '\n';
        } else if (c == 2) {
            int idx = -1;
            int st = 1, dr = n;

            while (st <= dr) {
                int mid = st + (dr - st) / 2;

                if (v[mid] >= x) {
                    idx = mid;
                    dr = mid - 1;
                } else
                    st = mid + 1;
            }
            fout << idx << '\n';
        }
    }

    return 0;
}