#include<fstream>
#include<algorithm>
using namespace std;

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

const int NMAX = 100009;
int n, m, t, x, v[NMAX];

int main()
{
    f >> n;
    for(int i = 1; i <= n; ++i) f >> v[i];
    sort(v + 1, v + n + 1);
    f>>m;
    int poz;
    for(; m; --m)
    {
        f >> t >> x;
        if(!t)
        {
            poz = upper_bound(v + 1, v + n + 1, x) - v - 1;
            if(poz <= n && poz >= 1 && v[poz] == x) g << poz << '\n';
            else g << -1 << '\n';
        }
        else
        if(t == 1)
        {
            poz = upper_bound(v + 1, v + n + 1, x) - v - 1;
            if(poz <= n && poz >= 1 && v[poz] == x) g << poz << '\n';
            else
            {
                while(poz > n || poz < 1 || v[poz] != x)
                    poz = upper_bound(v + 1, v + n + 1, --x) - v;
                g << poz <<'\n';
            }
        }
        else
        {
            poz = lower_bound(v + 1, v + n + 1, x) - v;
            if(poz <= n && poz >= 1 && v[poz] == x) g << poz << '\n';
            else
            {
                while(poz > n || poz < 1 || v[poz] != x)
                    poz = lower_bound(v + 1, v + n + 1, --x) - v;
                g << poz << '\n';
            }
        }
    }
}