#include <fstream>

#define Nmax 100100

using namespace std;

int logN, N, M, A[Nmax];

int binarySearch(int type, int Value) {

    int i, Step;

    Step = logN;

    if(type < 2) {

        for(i = 0; Step; Step >>= 1)
            if(i + Step <= N && A[i + Step] <= Value)
                i += Step;

        if(type == 0 && A[i] != Value)
            return -1;

        return i;

        }
    else
        for(i = N; Step; Step >>= 1)
            if(i - Step > 0 && A[i - Step] >= Value)
                i -= Step;

        return i;

}
void Read(ifstream & in) {

    in >> N;

    for(int i = 1; i <= N; i++)
        in >> A[i];

    in >> M;

}
int main() {

    int x, type;
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");

    Read(in);

    for(logN = 1; logN <= N; logN <<= 1);

    while(M--) {

        in >> type >> x;
        out << binarySearch(type, x) << '\n';

        }

    in.close();
    out.close();

    return 0;
}