#include<fstream>
#define InFile  "cautbin.in"
#define OutFile "cautbin.out"
#define MAX 100001

using namespace std;

ifstream fin  (InFile);
ofstream fout (OutFile);

int x[MAX];
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 ()
{
    fin >> n;
    for (i=1; i<=n; i++)
        fin >> x[i];
    fin >> m;
    for (i=1; i<=m; i++)
    {
        fin >> a >> b;
        poz = cb1 (b);
        if (a == 0)
            if (x[poz] == b)
                fout << poz << "\n";
            else
                fout << -1 << "\n";
        else
            if (a == 1)
                fout << poz << "\n";
            else
                fout << cb3 (b) << "\n";
    }
    return 0;
}