#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int main() {
    int n, m;
    cin >> n;
    vector<long long> sir(n);
    for (int i = 0; i < n; i++) {
        cin >> sir[i];
    }
    cin >> m;
    while (m > 0) {
        long long nr,intrebarea;
        cin >> intrebarea >> nr;
        if (intrebarea == 0) {
                auto PozNrPotrivit = upper_bound(sir.begin(), sir.end(), nr);
                if (PozNrPotrivit != sir.end()) {
                    cout << (PozNrPotrivit - sir.begin()) << endl;
                }
                else {
                    cout << -1 << endl;
                }
        }
        else if (intrebarea == 1) {
            int dreapta = n - 1;
            int stanga = 0;
            int mijloc = stanga + (dreapta - stanga) / 2;
            int celMaiMic = mijloc;
            while (stanga <= dreapta) {
                if (sir[mijloc] == nr) {
                    break;
                }
                if (sir[mijloc] < nr) {
                    stanga = mijloc + 1;
                }
                else {
                    dreapta = mijloc - 1;
                    celMaiMic = dreapta;
                }
                mijloc = stanga + (dreapta - stanga) / 2;
            }
            if (stanga > dreapta) {
                cout << celMaiMic+1 << endl;
            }
            else {
                int k = mijloc + 1;
                while (sir[mijloc] == sir[k]) {
                    mijloc++;
                    k++;
                }
                cout << mijloc+1 << endl;
            }
        }
        else {
            long long PozNrPotrivit = lower_bound(sir.begin(), sir.end(), nr) - sir.begin();
            cout << PozNrPotrivit + 1;
        }
        m--;
    }
    return 0;
}