#include <bits/stdc++.h>
using namespace std;

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

int V[1000001];

int main() {
    int N, M, x, y, i, t;
    fin >> N;
    for (i = 1; i <= N; ++i)
        fin >> V[i];
    fin >> M;
    for (i = 1; i <= M; ++i) {
        fin >> t >> y;
        if (t == 0) {
            x = upper_bound(V + 1, V + N + 1, y) - V - 1;
            if (x <= N && x >= 1 && V[x] == y)
                fout << x << "\n";
            else
                fout << "-1\n";
        } else if (t == 1) {
            x = lower_bound(V + 1, V + N + 1, y + 1) - V - 1;
            fout << x << "\n";
        } else {
            x = upper_bound(V + 1, V + N + 1, y - 1) - V;
            fout << x << "\n";
        }
    }
    return 0;
}