#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int a[100001];
int main()
{
    int n,m,i,x,y,st,dr,mij;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a[i];
    }
    fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        if(x==0)
        {
            st=1;
            dr=n+1;
            while(dr-st>1)
            {
                mij=(dr+st)/2;
                if(a[mij]>y)
                    dr=mij;
                else
                    st=mij;
            }
            if(a[st]==y)fout<<st;
            else fout<<-1;
            fout<<'\n';
        }
        else if(x==1)
        {
            st=1;
            dr=n+1;
            while(dr-st>1)
            {
                mij=(dr+st)/2;
                if(a[mij]>y)
                    dr=mij;
                else
                    st=mij;
            }
            if(a[st]<=y)fout<<st;
            fout<<'\n';
        }
        else
        {
            st=1;
            dr=n+1;
            while(dr-st>1)
            {
                mij=(dr+st)/2;
                if(a[mij]<y)
                    st=mij;
                else
                    dr=mij;
            }
            if(dr==n+1)fout<<st;
            else
            if(a[st]>=y)fout<<st;
            else fout<<dr;
            fout<<'\n';
        }
    }
    fin.close();
    fout.close();
    return 0;
}