#include <fstream>

using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int v[100005];
int main()
{int mij,n,m,tip,nr,i,p,u;
in>>n;
for(i=1;i<=n;i++)
    in>>v[i];
in>>m;
for(i=1;i<=m;i++)
{p=1;u=n;
    in>>tip>>nr;
    if(tip==0)
    {
        while(p<=u)
        {
            mij=(p+u)/2;
            if(v[mij]<=nr)
                p=mij+1;
            else
                u=mij-1;
        }
        mij=(p+u)/2;

    if (v[mij]>nr)mij--;
    if (v[mij]==nr)
        out<<mij<<'\n';
    else out<<-1<<'\n';
    }
    if(tip==1)
    {
        while(p<u)
        {
            mij=(p+u)/2;
            if(v[mij]<=nr)
                p=mij+1;
            else
                u=mij;
        }
        mij=(p+u)/2;
        if(v[mij]>nr) mij--;
        out<<mij<<'\n';

    }
    if(tip==2)
    {
        while(p<u)
        {
            mij=(p+u)/2;
            if(v[mij]<nr)
                p=mij+1;
            else
                u=mij;
        }
        mij=(p+u)/2;
        if(v[mij]<nr) mij++;
        out<<mij<<'\n';

    }
}
    return 0;
}