#include <cstdio>
#include <algorithm>
using namespace std;

#define Nmax 100002

FILE *f = fopen ( "cautbin.in", "r" );
FILE *g = fopen ( "cautbin.out", "w" );

int v[Nmax];

int main(){

    int N, M, type, val, poz;

    fscanf ( f, "%d", &N );
    for ( int i = 1; i <= N; ++i )
        fscanf ( f, "%d", &v[i] );

    fscanf ( f, "%d", &M );

    for ( int i = 1; i <= M; ++i ){
        fscanf ( f, "%d%d", &type, &val );

        if ( type == 0 ){
            poz = upper_bound ( v + 1, v + N + 1, val ) - v;

            if ( v[poz-1] == val )
                fprintf ( g, "%d\n", poz-1 );
            else
                fprintf ( g, "-1\n" );

            continue;
        }
        if ( type == 1 ){
            poz = upper_bound ( v + 1, v + N + 1, val ) - v;
            fprintf ( g, "%d\n", poz - 1 );
            continue;
        }
        if ( type == 2 ){
            poz = lower_bound ( v + 1, v + N + 1, val ) - v;
            fprintf ( g, "%d\n", poz );
        }
    }

    return 0;
}