#include <iostream>
#include <fstream>

using namespace std;

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

int main()
{
    unsigned int s, d, m;
    unsigned int N, M, i;
    unsigned int opcode, val;
    fin >> N;
    unsigned int a[N+1];
    for(i=1; i<=N; i++) fin >> a[i];
    fin >> M;
    for(i=0; i<M; i++) {
        fin >> opcode >> val;
        if(opcode == 0) {
            s = 1;
            d = N;
            while(s < d) {
                m = (s+d+1) / 2;
                if(a[m] <= val) {
                    s = m;
                } else {
                    d = m-1;
                }
            }
            if(a[d] != val) {
                fout << -1 << '\n';
            } else {
                fout << d << '\n';
            }
        } if(opcode == 1) {
            s = 1;
            d = N;
            while(s < d) {
                m = (s+d+1) / 2;
                if(a[m] <= val) {
                    s = m;
                } else {
                    d = m-1;
                }
            }
            fout << d << '\n';
        } if(opcode == 2) {
            s = 1;
            d = N;
            while(s < d) {
                m = (s+d) / 2;
                if(a[m] < val) {
                    s = m+1;
                } else {
                    d = m;
                }
            }
            fout << s << '\n';
        }
    }
    return 0;
}