#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n, q;
int v[100010];

void readAndSet() {
    fin >> n;

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

    fin >> q;
}

bool conditie(int valMij, int x, int c) {
    if (c < 2)
        return valMij <= x;
    return valMij < x;
}

int poz(int st, int x, int c) {
    if (c == 0) {
        if (v[st] == x)
            return st;
        if (st > 1 && v[st - 1] == x)
            return st - 1;
        return -1;
    }

    if (c == 1) {
        if (v[st] <= x)
            return st;
        return st - 1;
    }

    return st;
}

int cautBin(int x, int c) {
    int st = 1, dr = n;

    while (st < dr) {
        int mij = (st + dr) / 2;

        if (conditie(v[mij], x, c))
            st = mij + 1;
        else
            dr = mij;
    }

    return poz(st, x, c);
}

void solveQueries() {
    while (q--) {
        int c, x;

        fin >> c >> x;

        fout << cautBin(x, c) << '\n';
    }
}

int main() {
    readAndSet();
    solveQueries();
    return 0;
}