#include <fstream>
#include <algorithm>

using namespace std;

const int Nmax = 100005;

int n, a[Nmax];

int main() {
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin >> n;
    for(int i = 1; i <= n; i++) {
        fin >> a[i];
    }
    int m;
    fin >> m;
    while(m--) {
        int tip, x;
        fin >> tip >> x;
        if(tip == 0) {
            // upper_bound => gaseste primul element mai mare STRICT ca x
            // returneaza un pointer (a + 5, nu 5)
            // daca nu exista, returneaza a + n + 1
            // a = [1 3 9], x = 5
            int p = upper_bound(a + 1, a + n + 1, x) - a;
            if(p - 1 > 0 && a[p - 1] == x) {
                fout << p - 1 << "\n";
            }
            else {
                fout << "-1\n";
            }
        }
        else if(tip == 1) {
            int p = upper_bound(a + 1, a + n + 1, x) - a;
            if(p - 1 > 0) {
                fout << p - 1 << "\n";
            }
            else {
                fout << "-1\n";
            }
        }
        else {
            // a = [1 3 5 5 9], x = 5
            // lower_bound => gaseste primul element mai mare SAU EGAL ca x
            int p = lower_bound(a + 1, a + n + 1, x) - a;
            if(p <= n) {
                fout << p << "\n";
            }
            else {
                fout << "-1\n";
            }
        }
    }
}