#include <fstream>
#include <vector>

using namespace std;

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");

int v[100001];

int main()
{
    int n, m, m1, x, c0;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> v[i];
    cin >> m;

    for (int i = 1; i <= m; ++i) {
        cin >> m1 >> x;

        if (m1 == 0) { // Căutare exactă pentru valoarea x
            int st = 1, dr = n;
            c0 = -1;  // Resetăm c0 pentru fiecare interogare

            while (st <= dr) {
                int mid = (st + dr) / 2;
                if (x == v[mid]) {
                    c0 = mid;  // Actualizăm c0 la fiecare găsire
                    st = mid + 1; // Continuăm căutarea pentru a găsi ultima apariție
                } else if (x < v[mid]) {
                    dr = mid - 1;
                } else {
                    st = mid + 1;
                }
            }

            cout << c0 << endl;
        }

        if (m1 == 1) { // Căutare pentru cel mai mare element <= x
            int st = 1, dr = n;
            c0 = -1;

            while (st <= dr) {
                int mid = (st + dr) / 2;
                if (x >= v[mid]) {
                    c0 = mid; // Actualizăm c0 la fiecare valoare mai mică sau egală cu x
                    st = mid + 1; // Continuăm căutarea pentru a găsi cea mai mare poziție
                } else {
                    dr = mid - 1;
                }
            }

            cout << c0 << endl;
        }

        if (m1 == 2) { // Căutare pentru cel mai mic element >= x
            int st = 1, dr = n;
            c0 = -1;

            while (st <= dr) {
                int mid = (st + dr) / 2;
                if (v[mid] >= x) {
                    c0 = mid; // Actualizăm c0 la fiecare valoare mai mare sau egală cu x
                    dr = mid - 1; // Continuăm căutarea pentru a găsi cea mai mică poziție
                } else {
                    st = mid + 1;
                }
            }

            cout << c0 << endl;
        }
    }

    return 0;
}