#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5;

int v[NMAX + 1];

int main() {
    ifstream fin( "cautbin.in" );
    ofstream fout( "cautbin.out" );
    int n, m;
    fin >> n;
    for ( int i = 1; i <= n; i ++ ) {
        fin >> v[i];
    }
    fin >> m;
    for ( int i = 1, tip, x; i <= m; i ++ ) {
        fin >> tip >> x;
        if ( tip == 0 ) {
            int poz = upper_bound( v + 1, v + n + 1, x ) - v;
            if ( poz > 0 && v[poz - 1] == x ) {
                fout << poz - 1 << '\n';
            } else {
                fout << "-1\n";
            }
        } else if ( tip == 1 ) {
            int poz = upper_bound( v + 1, v + n + 1, x ) - v;
            fout << poz - 1 << '\n';

        } else {
            int poz = lower_bound( v + 1, v + n + 1, x ) - v;
            fout << poz << '\n';
        }
    }
    return 0;
}