#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,indice,i,x,mij,st,dr,ok,okk,v[100010],m,o,mijprec,mij1;
int main()
{
    f>>n;
    for(i=1; i<=n; i++)
    {
        f>>v[i];
    }
    f>>m;
    for(o=1; o<=m; o++)
    {
        f>>indice>>x;
        mijprec=0;
        st=1;
        dr=n;
        ok=0;
            while(st<=dr && ok==0)
            {
                mij=st+(dr-st)/2;
                if(x==v[mij])
                {
                    while(v[mij+1]==v[mij])
                        mij++;
                    ok=1;
                    break;
                }
                else
                {
                    if(x<v[mij])
                    {
                        dr=mij-1;
                    }
                    else
                    {
                        if(x>v[mij])
                        {
                            st=mij+1;
                        }
                    }
                }
            }
            if(indice==0)
                {if(ok==1)g<<mij<<'\n';
                else
                    g<<-1<<'\n';
                }
            else
                if(indice==1)
            {
                if(ok==1)
                    g<<mij<<'\n';
                else
                g<<dr<<'\n';
            }
            else
            {
                if(ok==1)
                {
                    mij1=mij;
                     while(v[mij1-1]==v[mij1])
                        mij1--;
                        g<<mij1<<'\n';
                }
                else
                g<<st<<'\n';
            }

    }
    return 0;
}