#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;

const char Input[] = "cautbin.in";
const char Output[] = "cautbin.out";

const int Dim = 100001;

int N, M;
vector <int> a;

int main() {

    ifstream fin( Input );
    ofstream fout( Output );

    int i, p, t, x;

    fin >> N;
    a.resize( N );
    for( i = 0; i < N; ++i )
        fin >> a[i];

    fin >> M;
    while( M-- ) {

        fin >> t >> x;
        if( t == 0 ) {

            p = int( upper_bound( a.begin(), a.end(), x ) - a.begin() - 1 );
            if( a[p] == x )
                fout << p + 1 << "\n";
            else
                fout << "-1\n";
        }
        else if( t == 1 ) {

            p = int( upper_bound( a.begin(), a.end(), x ) - a.begin() - 1 );
            fout << p + 1 << "\n";
        }
        else {

            p = int( lower_bound( a.begin(), a.end(), x ) - a.begin() );
            fout << p + 1 << "\n";
        }
    }

    fin.close();
    fout.close();

    return 0;
}