#include <fstream>

using namespace std;

#define MaxN 100001

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n, m, op, x, st, dr, mid;
int a[MaxN];

int main() {

    fin >> n;

    for ( int i = 1; i <= n; ++i )
        fin >> a[i];

    fin >> m;

    while(m--) {
        fin >> op >> x;
        st = 1, dr = n;
        if ( op == 0 ) {
            while( st <= dr ) {
                mid = st + (dr - st) / 2;
                if ( a[mid] >  x )
                    dr = mid - 1;
                else
                    st = mid + 1;
            }
            if ( a[dr] == x )
                fout << dr << '\n';
            else fout << "-1\n";
        }
        if ( op == 1 ) {
            while( st < dr ) {
                mid = st + (dr - st) / 2;
                if ( a[mid] >  x )
                    dr = mid - 1;
                else
                    st = mid + 1;
            }
            if ( a[dr] > x )
                dr--;
            fout << dr << '\n';
        }
        if ( op == 2 ) {
            while( st < dr ) {
                mid = st + (dr - st) / 2;
                if ( a[mid] >=  x )
                    dr = mid - 1;
                else
                    st = mid + 1;
            }
            if ( a[dr] < x )
                dr++;
            fout << dr << '\n';
        }

    }


}