#include <bits/stdc++.h>

const int MAXN = 100000;

using namespace std;

int v[MAXN + 5];

int main() {
    ifstream cin( "cautbin.in" );
    ofstream cout( "cautbin.out" );
    int n, m;
    cin >> n;
    for ( int i = 0; i < n; i++ ) {
        cin >> v[i];
    }
    cin >> m;
    for ( int i = 0; i < m; i++ ) {
        int op, x, ans = -1;
        int ans2 = -1;
        cin >> op >> x;
        int st = 0, dr = n - 1;
        if ( op == 0 ) {
            while ( st <= dr ) {
                int mij = ( st + dr ) / 2;
                if ( v[mij] == x ) {
                    ans = mij;
                    st = mij + 1;
                    ans2 = v[mij];
                }
                else if ( v[mij] < x ) {
                    st = mij + 1;
                }
                else {
                    dr = mij - 1;
                }
            }
        }
        else if ( op == 1 ) {
            while ( st <= dr ) {
                int mij = ( st + dr ) / 2;
                if ( v[mij] <= x ) {
                    ans = mij;
                    st = mij + 1;
                }
                else {
                    dr = mij - 1;
                }
            }
        }
        else {
            while ( st <= dr ) {
                int mij = ( st + dr ) / 2;
                if ( v[mij] < x ) {
                    st = mij + 1;
                }
                else {
                    ans = mij;
                    dr = mij - 1;
                }
            }
        }
        if ( ans == -1 ) {
            cout << ans << '\n';
        }
        else {
            cout << ans + 1 << '\n';
        }
    }

    return 0;
}