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

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n, m, id, x, v[100001];

int binarySearch(int element) {
    ll left = 1, right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;

        if (v[mid] < element)
            left = mid + 1;
        else
            right = mid;
    }

    return left;
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> v[i];
   fin >> m;
    for (int i = 1; i <= m; i++) {
        fin >> id >> x;

        if (!id) {
            int pos = binarySearch(x + 1) - 1;
            if (v[pos] == x)
                fout << pos << '\n';
            else if (pos + 1 <= n && v[pos + 1] == x)
                fout << pos + 1 << "\n";
            else
             fout << "-1\n";
        } else if (id == 2)
           fout << binarySearch(x) << '\n';
        else {
            int pos = binarySearch(x + 1) - 1;
            if (pos + 1 <= n && v[pos + 1] == x)
                fout << pos + 1 << '\n';
            else
                fout <<pos << "\n";
        }
    }

    return 0;
}