#include <fstream>
#include <algorithm> // pentru sort
using namespace std;
#include <fstream>
using namespace std;

int v[100001];

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

    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> v[i];

    int M;
    cin >> M;
    for (int q = 0; q < M; q++) {
        int type, x;
        cin >> type >> x;

        if (type == 0) { // cea mai mare pozitie a lui x
            int st = 1, dr = N, ans = -1;
            while (st <= dr) {
                int mid = st + (dr - st) / 2;
                if (v[mid] == x) {
                    ans = mid; // retinem pozitia
                    st = mid + 1; // cautam mai in dreapta
                } else if (v[mid] < x) {
                    st = mid + 1;
                } else {
                    dr = mid - 1;
                }
            }
            cout << ans << "\n";
        }

        else if (type == 1) { // cea mai mare pozitie cu element <= x
            int st = 1, dr = N, ans = -1;
            while (st <= dr) {
                int mid = st + (dr - st) / 2;
                if (v[mid] <= x) {
                    ans = mid;
                    st = mid + 1;
                } else {
                    dr = mid - 1;
                }
            }
            cout << ans << "\n";
        }

        else if (type == 2) { // cea mai mica pozitie cu element >= x
            int st = 1, dr = N, ans = -1;
            while (st <= dr) {
                int mid = st + (dr - st) / 2;
                if (v[mid] >= x) {
                    ans = mid;
                    dr = mid - 1;
                } else {
                    st = mid + 1;
                }
            }
            cout << ans << "\n";
        }
    }

    return 0;
}