#include <stdio.h>

#define NMAXX 100000

int v[NMAXX];

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

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

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

    fscanf( fin, "%d", &t );
    for ( i = 0; i < t; i++ ) {
        fscanf( fin, "%d%d", &cer, &q );
        st = 0;
        dr = n;
        while ( dr - st > 1 ) {
            mij = (st + dr) / 2;
            if ( v[mij] > q )
                dr = mij;
            else
                st = mij;
        }
        if ( cer == 0 ) {
            if ( v[st] == q ) {
                while ( v[st] == q ) {
                    st++;
                }
                fprintf( fout, "%d\n", st );
            } else {
                fprintf( fout, "-1\n" );
            }
        } else if ( cer == 1 ) {
            while ( v[st] <= q ) {
                st++;
            }
            fprintf( fout, "%d\n", st );
        } else {
            while ( v[st] >= q ) {
                st--;
            }
            fprintf( fout, "%d\n", st + 2 );
        }
    }

    fclose( fin );
    fclose( fout );
    return 0;
}