#include <fstream>
#define lg_max 100001

using namespace std;

ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");

int sir[lg_max];
int poz, st, dr, mij, n, m;

void citire()
{
        fin>>n;
        for (int i=1;i<=n;i++)
            fin>>sir[i];
        fin>>m;
}

void caz1(int x)
{
    if (sir[n]==x)
    {
            poz=n;
        return ;
    }
    while (st<dr)
    {
        mij=(st+dr)>>1;
        if (x>=sir[mij])
            st=mij+1;
        else
            dr=mij;;
    }
if (sir[mij]==x)
    poz=mij;
else
    poz=-1;
}

void caz2(int x)
{
    while (st<dr)
    {
        mij=(st+dr)>>1;
        if (x>=sir[mij])
            st=mij+1;
        else
            dr=mij;
    }
    poz=(st+dr)>>1;
    if (x<sir[poz])
        poz--;
}

void caz3(int x)
{
    while (st<dr)
    {
        mij=(st+dr)>>1;
        if (x>sir[mij])
            st=mij+1;
        else
            dr=mij;
    }
    poz=(st+dr)>>1;
    if (x>sir[poz])
        poz--;
}

void afish()
{
    int ok,x;
    for (int i=0;i<m;i++)
    {
        st=1,dr=n;
        fin>>ok>>x;
        switch(ok)
        {
            case 0:{caz1(x); break;}
            case 1:{caz2(x); break;}
            default:{ caz3(x); break;}
        }
        fout<<poz<<"\n";
    }
}
int main ()
{
    citire();
    afish();
    return 0;
}