#include <cstdio>
#include <fstream>
#include <cstdlib>
#include <utility>
#include <algorithm>
#include <bitset>
#include <vector>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <cstring>

#define LL long long
#define F(i, a, b) for (int i = (a) ; i <= (b) ; ++i)
#define V_IN(x) (V).push_back((x))
#define LLU unsigned LL
#define ALL(V) (V).begin(), (V).end()
#define V_sz (V).size()
#define mlb map <LL, bool>
#define MLI map <LL, int>

#define mp make_pair
#define pii pair <int, int>
#define SORT(x) sort ((x).begin(), (x).end() )

#define fi first
#define se second
#define VI vector <int>

using namespace std;

VI V;

int lg, i, logg;

inline int b_s01 (int x, int N) {
    for (i = 0, logg = lg;  logg ; logg >>= 1)
    if (logg + i < N && V[logg + i] <= x)
    i += logg;
    return i;
}

inline int b_s02 (int x, int N){
    for (i = N - 1 , logg = lg; logg; logg >>= 1 )
        if (i - logg >= 0  && V[i - logg] >= x )
        i -= logg;
    return i;
}





int main(){
    ifstream f ("cautbin.in");
    ofstream out ("cautbin.out");
    int n, q, tip, r;
    f >> n;
    V.resize(n);
    for (auto &i : V) f >> i;
    f >> q;
    for (lg = 1; lg < n; lg <<= 1 );

    for (; q; --q ) {
            f >> tip >> r;
            if (tip == 1) {
                    out << b_s01(r, n) + 1 << "\n";
                    continue;
            }
            if (tip == 0) {
                    if (V[b_s01(r,n)] == r) out << b_s01(r,n) + 1 << "\n";
                    else out << -1 << "\n";
                    continue;
            }
            out << b_s02(r, n) + 1 << "\n";
    }
    return 0;


}