// programul raspunde la interogari prin cautari binare asupra unui sir ordonat

#include <bits/stdc++.h>
using namespace std;

int v[100001], n, m;

// tip 0: ultima pozitie a lui x sau -1
int caut0(int x) {
    int st = 0, dr = n - 1, rasp = -1;
    while (st <= dr) {
        int mid = st + (dr - st) / 2;
        if (v[mid] == x) {
            rasp = mid;
            st = mid + 1;
        } else if (v[mid] < x) {
            st = mid + 1;
        } else {
            dr = mid - 1;
        }
    }
    return rasp; // 0-based
}

// tip 1: ultima pozitie cu v[mid] <= x
int caut1(int x) {
    int st = 0, dr = n - 1, rasp = -1;
    while (st <= dr) {
        int mid = st + (dr - st) / 2;
        if (v[mid] <= x) {
            rasp = mid;
            st = mid + 1;
        } else {
            dr = mid - 1;
        }
    }
    return rasp; // 0-based
}

// tip 2: prima pozitie cu v[mid] >= x
int caut2(int x) {
    int st = 0, dr = n - 1, rasp = -1;
    while (st <= dr) {
        int mid = st + (dr - st) / 2;
        if (v[mid] >= x) {
            rasp = mid;
            dr = mid - 1;
        } else {
            st = mid + 1;
        }
    }
    return rasp; // 0-based
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> v[i];

    cin >> m;

    for (int i = 0; i < m; i++) {
        int tip, x;
        cin >> tip >> x;

        if (tip == 0)
            cout << caut0(x) << "\n";
        else if (tip == 1)
            cout << caut1(x) << "\n";
        else
            cout << caut2(x) << "\n";
    }

    return 0;
}