#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
long long n,m,b[1000001],i,x,y,st,dr,mij,gasit;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>b[i];
    f>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        if(x==0)
        {
        st=1;
        dr=n;
        gasit=0;
        while(st<=dr&&gasit==0)
        {
            mij=(st+dr)/2;
                if(b[mij]==y&&(b[mij+1]>y||mij==n))
            {
                gasit=1;
                g<<mij<<"\n";
            }

            if(b[mij]>=y)
                dr=mij-1;
else
st=mij+1;
        }
        if(gasit==0)
            g<<-1<<"\n";
        }
        if(x==1)
        {
            st=1;
        dr=n;
        gasit=0;
        while(st<=dr&&gasit==0)
        {
            mij=(st+dr)/2;
            if(b[mij]==y&&(b[mij+1]>y||mij==n))
            {
                gasit=1;
                g<<mij<<"\n";
            }

            if(b[mij]>=y)
                dr=mij-1;
else
st=mij+1;
        }
        }
        if(x==2)
        {
            st=1;
        dr=n;
        gasit=0;
        while(st<=dr&&gasit==0)
        {
            mij=(st+dr)/2;
            if(b[mij]==y&&(b[mij-1]<y||mij==1))
                {
                gasit=1;
                g<<mij<<"\n";
            }
            else
                dr=mij-1;
            if(b[mij]<=y)
                st=mij+1;
          else
                dr=mij-1;
        }
        }
    }

    return 0;
}