#include<fstream>

using namespace std;

int x[100010];
int n, i, m, a, b, poz;

int cb1 (int val)
{
    int st, p, med, last=-1;
    st = 1;
    p = n;
    while (st<=p)
    {
        med = (st+p)/2;
        if (val>=x[med])
        {
            last = med;
            st = med+1;
        }
        else
            p = med-1;
    }
    return last;
}

int cb3 (int val)
{

    int st, p, med, last=-1;
    st = 1;
    p = n;
    while (st<=p)
    {

        med = (st+p)/2;
        if (val<=x[med])
        {

            last = med;
            p = med-1;
        }
        else
            st = med+1;
    }
    return last;
}

int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f >> n;
    for (i=1; i<=n; i++)
        f >> x[i];
    f >> m;
    for (i=1; i<=m; i++)
    {
        f >> a >> b;
        poz = cb1(b);
        if (a==0)
            if (x[poz]==b)
                g << poz << "\n";
            else
                g << -1 << "\n";
        else
            if(a==1)
                g << poz << "\n";
            else
                g << cb3(b) << "\n";
    }
    return 0;
}