#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int main()
{
int n,m,op,x,i,st,dr,ok,mij,v[100005];
    fin>>n;
    for( i=1;i<=n;i++)
    fin>>v[i];
    fin>>m;
    while(m--)
    {
        fin>>op>>x;
         ok=0;
         st=1;
         dr=n+1;
        if(op==0)
        {

            while(st<dr)
            {
                mij=(st+dr)/2;
                if(v[mij]<=x)
                {
                    st=mij+1;
                    ok=mij;
                }
                else
                    dr=mij;
            }
            if(v[ok]!=x)
                ok=-1;
        }
        else if(op==1)
        {

            while(st<dr)
            {
                int mij=(st+dr)/2;
                if(v[mij]<=x)
                {
                    st=mij+1;
                    ok=mij;
                }
                else
                    dr=mij;
            }
        }
        else
        {
            while(st<dr)
            {
                mij=(st+dr)/2;
                if(v[mij]>=x)
                {
                    dr=mij;
                    ok=mij;
                }
                else
                    st=mij+1;
            }
        }
        fout<<ok<<"\n";
    }
    return 0;
}