#include <iostream>
#include <fstream>
//cerinta: https://infoarena.ro/problema/cautbin
// cerinta 2 nu merge
using namespace std;
long long int cerinta,li,ls,mij,v[100001],n,m,gasit=0,x,i;
int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i];
    li=1;
    ls=n;
    fin>>m;
    for (i=1;i<=m;i++)
    {
        li=1;
        ls=n;
        gasit=0;
        fin>>cerinta>>x;
        if (cerinta==0)
        {
            while ( li<=ls && (!gasit || ( gasit&&v[mij]==v[(li+ls)/2] ) ) )
            {
                mij=(li+ls)/2;
                if (v[mij]==x)
                {
                    gasit=1;
                    li=mij+1;
                }
                else if (v[mij]<x)
                    li=mij+1;
                else ls=mij-1;
            }
            if (gasit) cout<<mij;
                else cout<<-1;
        }
        if (cerinta==1)
        {
            while (li<=ls && v[(li+ls)/2]<=x)
            {
                mij=(li+ls)/2;
                if (v[mij]<=x)
                    li=mij+1;
                else ls=mij-1;
            }
            cout<<endl<<mij;
        }
        if (cerinta==2)
        {

            while (li<=ls && !gasit )
            {

                mij=(li+ls)/2;

                if (v[mij]>=x)
                    gasit=1;
                else li=mij+1;
            }
            if (gasit)
                while (v[mij-1]>=x&&(mij-1))
                {
                    mij--;
                }
            cout<<endl<<mij;
        }
    }

    fin.close();fout.close();
    return 0;
}