#include <iostream>
#include <fstream>
using namespace std;

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

const int maxn = 1e5 + 5;
int V[maxn];

int Bsearch_upper (int left, int right, int val) {
    int mid, pos = -1;
    while (left <= right) {
        mid = left + ((right - left) >> 1);
        if (V[mid] <= val) {
            pos = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return pos;
}

int Bsearch_lower (int left, int right, int val) {
    int mid, pos = -1;
    while (left <= right) {
        mid = left = ((right - left) >> 1);
        if (V[mid] >= val) {
            pos = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return pos;
}

int main() {
    ios_base :: sync_with_stdio (false);
    int n, m, i, type, val, pos;
    fin >> n;
    for (i = 1; i <= n; i++) {
        fin >> V[i];
    }
    fin >> m;
    for (i = 1; i <= m; i++) {
        fin >> type >> val;
        if (type == 0) {
            pos = Bsearch_upper(1, n, val);
            if (V[pos] == val) {
                fout << pos << '\n';
            } else {
                fout << "-1\n";
            }
        } else if (type == 1) {
            fout << Bsearch_upper(1, n, val) << "\n";
        } else {
            fout << Bsearch_lower(1, n, val) << "\n";
        }
    }
    fin.close();
    fout.close();
    return 0;
}