#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100000];
int main()
{
    int n,m,i,intr,ls,ld,mij,ok,x,imax,imin,j;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    for(j=1;j<=m;j++)
{
        fin>>intr>>x;
        ok=0;
        ls=1;
        ld=n;

        if(intr==0){
        while(ls<=ld && ok==0)
            {mij=(ls+ld)/2;
            if(x==v[mij])
                {
                    imax=mij;
                    ok=1;
                }
            else if(x>v[mij])
                ls=mij+1;
            else
                ld=mij-1;
            }
        if(ok==1)
        {
            for(i=imax+1;i<=n;i++)
        {
            if(x==v[i])
                imax=i;
        }
        fout<<imax;
        }
        else
            fout<<-1;
        }
        else if(intr==1)
        {
            while(ls<=ld && ok==0)
            {mij=(ls+ld)/2;
            if(v[mij]<=x)
                {
                    imax=mij;
                    ok=1;
                }
            else
                ld=mij-1;

            }
            for(i=mij+1;i<=n;i++)
            {
                if(v[i]<=x)
                    imax=i;
            }
            fout<<imax;
        }
        else
        {
            while(ls<=ld && ok==0)
            {mij=(ls+ld)/2;
            if(v[mij]>=x)
                {
                    imin=mij;
                    ok=1;
                }
            else if(x>v[mij])
                ls=mij+1;
            else
                ld=mij-1;
            }
            for(i=mij-1;i>=1;i--)
            {
                if(v[i]>=x)
                    imin=i;
            }
            fout<<imin;
        }
        fout<<endl;
}

    return 0;
}