#include <fstream>
#include <iostream>
#define DN 100005
using namespace std;
 
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
   
// ifstream fin("input.txt");
// ofstream fout("output.txt");
 
int a[DN];
 
int bs_last_smaller(const int &n, const int &x) {
    // returns the position of the last element in a[] which is <= x.
    // returns -1 if there is no such element.
    int lo = -1, hi = n, mid;
    while (hi > lo + 1) {
        mid = (lo + hi) / 2;
        if (x < a[mid])
            hi = mid;
        else
            lo = mid;
    }
    return lo;
}
 
int bs_first_greater(const int &n, const int &x) {
    // returns the position of the first element in a[] which is >= x.
    // returns n if there is no such element.
    int lo = -1, hi = n, mid;
    while (hi > lo + 1) {
        mid = (lo + hi) / 2;
        if (x <= a[mid])
            hi = mid;
        else
            lo = mid;
    }
    return hi;
}
 
int main() {
    int n, t, x, q, pos;
    fin >> n;
    for(int i = 0; i < n; ++i) {
        fin >> a[i];
    }
 
    fin >> q;
    for (int i = 0; i < q; ++i) {
        fin >> t >> x;
        if (t == 0) {
            pos = bs_last_smaller(n, x);
            if (pos != -1 && a[pos] == x)
                ++pos;
            else
                pos = -1;
        } else if (t == 1) {
            pos = bs_last_smaller(n, x) + 1;
        } else {
            pos = bs_first_greater(n, x) + 1;
        }
        fout << pos << '\n';
 
    }
    return 0;
}