#include <stdio.h>

#define MAX_N 100000

int v[MAX_N];

int main() {
    FILE *fin, *fout;
    int n, q, tip, x, st, dr, mij, i;

    fin = fopen( "cautbin.in", "r" );

    fscanf( fin, "%d", &n );
    for ( i = 0; i < n; i++ )
        fscanf( fin, "%d", &v[i] );

    fout = fopen( "cautbin.out", "w" );

    fscanf( fin, "%d", &q );
    for ( i = 0; i < q; i++ ) {
        fscanf( fin, "%d%d", &tip, &x );

        if ( tip == 0 ) {
            st = 0;
            dr = n;
            while ( dr - st > 1 ) {
                mij = (st + dr) / 2;
                if ( v[mij] > x )
                    dr = mij;
                else
                    st = mij;
            }

            fprintf( fout, "%d\n", v[st] == x ? st + 1 : -1 );
        }
        else if ( tip == 1 ) {
            st = 0;
            dr = n;
            while ( dr - st > 1 ) {
                mij = (st + dr) / 2;
                if ( v[mij] > x )
                    dr = mij;
                else
                    st = mij;
            }

            fprintf( fout, "%d\n", st + 1 );
        }
        else {
            st = -1;
            dr = n - 1;
            while ( dr - st > 1 ) {
                mij = (st + dr) / 2;
                if ( v[mij] < x )
                    st = mij;
                else
                    dr = mij;
            }

            fprintf( fout, "%d\n", dr + 1 );
        }
    }

    fclose( fin );
    fclose( fout );

    return 0;
}