#include <bits/stdc++.h>
#define MAXN 100000

using namespace std;

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

int main() {
    int n, m, arr[MAXN];
    fin >> n;
    for (int i = 0; i < n; i++)
        fin >> arr[i];
    fin >> m;
    for (int q = 0; q < m; q++) {
        int t, x;
        fin >> t >> x;
        if (t == 0) {
            int pos = upper_bound(arr, arr + n, x) - arr;
            fout << (arr[pos - 1] == x ? pos : -1) << '\n';
        } else if (t == 1) {
            fout << upper_bound(arr, arr + n, x) - arr << '\n';
        } else {
            fout << lower_bound(arr, arr + n, x) - arr + 1 << '\n';
        }
    }
    return 0;
}