#include <fstream>

using namespace std;
ifstream f("date.in");
ofstream g("date.out");

int v[100000],i,j,k,ok,n,st,dr,c,mij,x;
int main()
{
    f>>n;
    for(i=1;i<=n;++i)
        f>>v[i];
    f>>k;
    for(i=1;i<=k;++i)
    {
        f>>c>>x;
        st=1;dr=n;
        ok=0;
        while(st<=dr&&!ok)
        {
            mij=st+(dr-st)/2;
            if(mij==x)
                ok=1;
            else
                if(x<mij)
                dr=mij-1;
            else
                st=mij+1;
        }
    if(c==0)
    {
        ok=-1;
        for(j=mij;j<=n;j++)
            if(v[j]!=x)
                {ok=j-1;break;}
        g<<ok<<'\n';
    }
    else
        if(c==1)
    {
        if(ok==1)
        {
           for(j=mij;j<=n;j++)
            if(v[j]!=x)
                {ok=j-1;break;}
        g<<ok<<'\n';
        }
        else
            g<<mij-1<<'\n';
    }
    else
    {
        if(ok==1)
        {
           for(j=mij;j>=1;j--)
            if(v[j]!=x)
                {ok=j+1;break;}
        g<<ok<<'\n';
        }
        else
            g<<mij<<'\n';
    }
    }
    return 0;
}