#include <fstream>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int n,m,p,i,j,st,dr,mij,vcautata,pozitia;
int nr[1000005];

int main()
{
    f>>n;

    for(i=1;i<=n;i++)
    {
        f>>nr[i];
    }

    f>>m;

    for(j=1;j<=m;j++)
    {
        f>>p>>vcautata;

        st=1;
        dr=n;
        pozitia=0;

        if(p==0)
        {
            while(st<=dr)
            {
                mij=(st+dr+1)/2;
                if(nr[mij]>vcautata)
                {
                    dr=mij-1;
                }
                else
                if(nr[mij]==vcautata)
                {
                    pozitia=mij;
                    st=mij+1;
                }
                else
                {
                    st=mij+1;
                }
            }
            if(pozitia!=0)
            {
                g<<pozitia<<'\n';
            }
            else
            {
                g<<-1<<'\n';
            }
        }
        else if(p==1)
        {
            while(st<=dr)
            {
                mij=(st+dr+1)/2;
                if(nr[mij]>vcautata)
                {
                    dr=mij-1;
                }
                else
                if(nr[mij]<=vcautata)
                {
                    pozitia=mij;
                    st=mij+1;
                }
            }
            g<<pozitia<<'\n';
        }
        else
        {
            while(st<=dr)
            {
                mij=(st+dr+1)/2;

                if(nr[mij]>=vcautata)
                {
                    pozitia=mij;
                    dr=mij-1;
                }
                else
                {
                    st=mij+1;
                }
            }
            g<<pozitia<<'\n';
        }

    }

    return 0;
}