#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 = 0; i < n; i++)
        fin >> v[i];

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

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

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

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

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

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

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

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

    return 0;
}