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

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int a[100000];

int main () {
    int n, m;
    f >> n;

    int i, p, x, y;
    for(i = 1; i <= n; i++)
        f >> a[i];
    f >> m;



    for (i = 1; i <= m; i++) {
        f >> p >> y;

        if (p == 0) {
            x = upper_bound(a + 1, a + n + 1, y) - a - 1;
            if (x <= n && x >= 1 && a[x] == y)
                g << x << endl;
            else
                g << -1 << endl;;
        } else if (p == 1) {
            x = lower_bound(a + 1, a + n + 1, y + 1) - a - 1;
            g << x << endl;
        } else {
            x = upper_bound(a + 1, a + n + 1, y - 1) - a;
            g << x << endl;
        }
    }
    return 0;
}