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

using namespace std;

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

int n, m, t, x, a[100001];

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> a[i];
    fin >> m;
    for (int i = 1; i <= m; i++) {
        fin >> t >> x;
        // fiindca lucram cu array-uri indexate de la 1, trebuie sa scadem - a - 1 la final
        if (t == 0) {
            int tmp = upper_bound(a + 1, a + n + 1, x) - a - 1;
            if (tmp > n || tmp < 1 || a[tmp] != x)
                fout << "-1" << "\n";
            else
                fout << tmp << "\n";
        }
        else if (t == 1) {
            int tmp = lower_bound(a + 1, a + n + 1, x + 1) - a - 1;
            fout << tmp << "\n";
        }
        else {
            int tmp = upper_bound(a + 1, a + n + 1, x - 1) - a;
            fout << tmp << "\n";
        }
    }
    return 0;
}