using namespace std;
#include<iostream>
#include<fstream>
#include<algorithm>

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

    int n;

    fin >> n;

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

    int m;

    fin >> m;

    for (int i = 1; i<=m; i++) {
        int cerinta;
        int x;

        fin >> cerinta;
        fin >> x;

        int st = 1;
        int dr = n;

        if (cerinta == 0) {
            int pozmax = -1;

            while (st <= dr) {
                int mid = (st + dr) / 2;
                if (x > v[mid]) {
                    st = mid + 1;
                } else if (x < v[mid]) {
                    dr = mid - 1;
                } else {
                    pozmax = mid;
                    break;
                }
            }
            if (pozmax != -1) {
                while (x == v[pozmax+1] && pozmax < n) {
                    pozmax++;
                }
            }
            fout << pozmax << "\n";
        } else if (cerinta == 1) {
              int poz = -1;
              while (st <= dr) {
                int mid = (st + dr) / 2;
                if (v[mid] <= x) {
                    poz = mid;
                    st = mid+1;
                } else {
                    dr = mid - 1;
                }
            }
            if (poz != -1) {
                while (x == v[poz+1] && poz < n) {
                    poz++;
                }
            }
            fout << poz << "\n";
        } else if (cerinta == 2) {
            int poz = -1;
            while (st <= dr) {
                int mid = (st + dr) / 2;
                if (v[mid] >= x) {
                    poz = mid;
                    dr = mid - 1;
                } else {
                    st = mid + 1;
                }
            }
            if (poz != -1) {
                while (x == v[poz-1] && poz > 1) {
                    poz--;
                }
            }
            fout << poz << "\n";
        }
    }


    fin.close();
    fout.close();

    return 0;
}