#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

class ifbuffer {
    private:
        char text[100000];
        int size;
        int pos;
        bool isDigit[128];

        FILE *file;

        inline void refill( void ) {
            pos = 0;
            fread( text, 1, size, file );
        }

        inline char getc() {
            char c = text[pos ++];

            if ( pos == size )
                refill();

            return c;
        }

        inline int getnr() {
            char c = getc();
            int nr = 0;

            while ( !isDigit[c] )
                c = getc();
            while ( isDigit[c] ) {
                nr = nr * 10 + c - '0';
                c = getc();
            }

            return nr;
        }

    public:
        inline ifbuffer( char * path, int s = 100000 ) {
            size = s;

            file = fopen( path, "r" );

            int i;
            for ( i = 0; i < '0'; i ++ )
                isDigit[i] = false;
            for ( i = '0'; i <= '9'; i ++ )
                isDigit[i] = true;
            for ( i = '9' + 1; i < 128; i ++ )
                isDigit[i] = false;

            refill();
        }

        inline ifbuffer &operator>>( int &v ) {
            v = getnr();
            return *this;
        }

        inline ifbuffer &operator>>( char &v ) {
            v = getc();
            return *this;
        }

        inline void close() {
            fclose( file );
        }
};

class ofbuffer {
    private:
        char text[100000];
        int size;
        int pos;
        bool isDigit[128];

        FILE *file;

        inline void clear( void ) {
            pos = 0;
            fwrite( text, 1, size, file );
        }

        inline void putc( char c) {
            text[pos ++] = c;

            if ( pos == size )
                clear();
        }

        inline void putnr( int nr ) {
            if ( nr < 0 ) {
                putc( '-' );
                nr =- nr;
            }

            int p10;
            for ( p10 = 1; p10 * 10LL <= nr; p10 *= 10 );
            for ( ; p10 > 0; p10 /= 10 )
                putc( nr / p10 % 10 + '0' );
        }

    public:
        inline ofbuffer( char * path, int s = 100000 ) {
            size = s;

            file = fopen( path, "w" );

            int i;
            for ( i = 0; i < '0'; i ++ )
                isDigit[i] = false;
            for ( i = '0'; i <= '9'; i ++ )
                isDigit[i] = true;
            for ( i = '9' + 1; i < 128; i ++ )
                isDigit[i] = false;
        }

        inline ofbuffer &operator<<( int v ) {
            fprintf( file, "%d", v );
            return *this;
        }

        inline ofbuffer &operator<<( char v ) {
            fputc( v, file );
            return *this;
        }

        inline void close() {
            fclose( file );
        }
};

ifbuffer in("cautbin.in");
ofbuffer out("cautbin.out");
int v[100003];
int n;

int lwb(int x) {
    int st = 1;
    int dr = n;
    int mid;
    int poz = n;

    while(st <= dr) {
        mid = st + (dr-st)/2;
        if(v[mid] < x)
            st = mid+1;
        else if(v[mid] > x)
            dr = mid-1;
        else
            poz = min(poz, mid), dr = mid-1;
    }

    return poz;

}

int main() {

    in >> n;

    for(int i = 1; i <= n; i++)
        in >> v[i];

    int q,x,y;
    in >> q;

    for(int i = 1; i <= q; i++) {

        in >> x >> y;

        if(x == 0) {
            int lw = lwb(y+1);
            if(lw == 1)
                out << -1 << '\n';
            else if(v[lw-1] != y)
                out << -1 << '\n';
            else
                out << lw-1 << '\n';
        } else if(x == 1) {
            int lw = lwb(y+1);
            if(lw == 1)
                out << lw << '\n';
            else
                out << lw-1 << '\n';
        } else {
            int lw = lwb(y);
            out << lw << '\n';
        }

    }

    return 0;
}