#include <bits/stdc++.h>

using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int n, a[100100], T, nr, x;
int main()
{
    in >> n;
    for(int i = 1;i <= n;i++)
        in >> a[i];
    sort(a + 1,a + n + 1);
    in >> T;
    for(int i = 1;i <= T;i++)
    {
        in >> nr >> x;
        if(nr == 0)
        {
            int nr = upper_bound(a + 1,a + n + 1, x) - a - 1;
            if(nr <= n && nr && a[nr] == x) out << nr << '\n';
            else out << -1 << '\n';
        }
        else if(nr == 1)
        {
            int nr = lower_bound(a + 1,a + n + 1, x + 1) - a - 1;
            out << nr << '\n';
        }
        else
        {
            x = upper_bound(a + 1,a + n + 1,x - 1) - a;
            out << x << '\n';
        }
    }
    return 0;
}