#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
int v[100001];

int binarySearch1(int v[], int left, int right, int value) {
    if (left == right) return left;
    int middle = (left + right) / 2;
    if (v[middle + 1] <= value){
        return binarySearch1(v, middle + 1, right, value);
    } else {
        return binarySearch1(v, left, middle,  value);
    }
}
int binarySearch2(int v[], int left, int right, int value) {
    if (left == right) return left;
    int middle = (left + right) / 2;
    if (v[middle] >= value){
        return binarySearch2(v, left, middle, value);
    } else {
        return binarySearch2(v, middle + 1, right, value);
    }
}

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

    int n, m;
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> v[i];
    }
    sort(v + 1, v + n + 1);

    fin >> m;
    for (int i = 1; i <= m; ++i) {
        int type, x, p;
        fin >> type >> x;;
        if (type == 0) {
        if (v[binarySearch1(v, 1, n, x)] == x) {
            p = binarySearch1(v, 1 , n, x);
        } else {
            p = -1;
        }
        }
        if (type == 1){
        p = binarySearch1(v, 1, n, x);
        }
        if (type == 2) {
        p = binarySearch2(v, 1, n, x);
        }
        fout << p << "\n";
    }
    return 0;
}