#include <fstream>

#define MAX_SIZE 100005

using namespace std;

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

int vSize, v[MAX_SIZE], qSize, position;

bool verify (int middle, int number, int type) {
    switch (type) {
        case 2: return (v[middle] >= number); break;
        default: return (v[middle] > number); break;
    }
}

int caut_bin (int type, int number, int left, int right) {
    while (left <= right) {
        int middle = (left + right) / 2;
        if (verify(middle, number, type))
            right = middle - 1;
        else left = middle + 1;
    }
    switch (type) {
        case 0: if (v[right] == number) return right;
                else return -1; break;
        case 1: return right; break;
        case 2: return left; break;
    }
}

int main () {
    int type, number;

    fin >> vSize;
    for (int i = 1; i <= vSize; ++i) {
        fin >> v[i];
    }

    fin >> qSize;
    for (int i = 1; i <= qSize; ++i) {
        fin >> type >> number;
        fout << caut_bin(type, number, 1, vSize) << "\n";
    }

    return 0;
}