#include <iostream>
#include<fstream>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int pozitie;

int cautbin( int inc,  int sf, int v[], int b)
{
 int mij=inc+(sf-inc)/2;
 if(inc>sf)
    return mij;
    if(b==v[mij])
        return mij;
    else
        if(b>v[mij])
            return cautbin(mij+1,sf,v,b);
            return cautbin(inc,mij-1,v,b);
}

int cautbin1( int inc,  int sf, int v[], int b)
{
    int mij;
    while(inc<sf)
    {
        mij=inc+(sf-inc)/2;
        if(v[mij]<=b)
            inc=mij;
        else
            sf=mij-1;
    }
    mij=(inc+sf)/2;
    if(v[mij]>b)
        mij--;
    return mij;
}
int cautbin2( int inc,  int sf, int v[], int b)
{


int mij;
    while(inc<sf)
    {
        mij=inc+(sf-inc)/2;
        if(v[mij]>=b)
            sf=mij;
        else
            inc=mij+1;
    }
    mij=(inc+sf)/2;
    if(v[mij]>b)
        mij--;
    return mij;

}
int main()
{
     int v[100000],i,j,n,mij,m;

    f>>n;
    for(int i=1;i<=n;i++)
        f>>v[i];

    f>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        f>>a>>b;
            if(a==0)
                {
                pozitie=cautbin(1,n,v,b);
                if(pozitie<1||pozitie>n)
                    g<<-1<<'\n';
                    else if(v[pozitie]!=b)
            g<<-1<<'\n';
             else
{

             while(b==v[pozitie]&&pozitie<=n)
                    pozitie++;
                    pozitie--;
                    g<<pozitie<<'\n';
}


                }
                else if (a==1)
                {
                    pozitie=cautbin1(1,n,v,b);
                while(b>=v[pozitie]&&pozitie<=n)
                    pozitie++;
                    pozitie--;
                                       g<<pozitie<<'\n';

                }
                else
                {
                    pozitie=cautbin2(1,n,v,b);


                    g<<pozitie<<'\n';
                }


    }


    return 0;
}