#include <fstream>
using namespace std;

ifstream fin( "cautbin.in" );
ofstream fout( "cautbin.out" );
const int NMAX=100001;
int n,a[NMAX],m,task,x;

int bs(int lf, int rg, int x)
{
    if (lf > rg) return -1;
    int mij = lf + (rg-lf)/2;
    if (a[mij] == x)
    {
        return max( mij, bs(mij+1,rg,x) );
    }
    else if ( a[mij]>x ){
        return bs(lf,mij-1,x);
    }
    else{
        return bs(mij+1,rg,1);
    }

}

int lb(int lf, int rg, int x)
{
    if ( lf > rg ) return -1;
    int mij = lf + (rg-lf)/2;
     if (a[mij] <= x)
    {
        return max( mij, lb(mij+1,rg,x) );
    }
    else 
        return lb(lf,mij-1,x);
}

int ub(int lf, int rg, int x)
{
    if ( lf > rg ) return NMAX;
    int mij = lf + (rg-lf)/2;
     if (a[mij] >= x)
    {
        return min( mij, ub(lf,mij-1,x) );
    }
    else 
        return ub(mij+1, rg ,x);
}

int main()
{
    fin>>n;
    for (int i=1;i<=n;++i)
    {
        fin>>a[i];
    }
    fin>>m;
    for (int i=1;i<=m;++i)
    {
        fin>>task>>x;
        if (task == 0) fout<<bs(1,n,x)<<'\n';
        else if (task==1)
        {
            fout<<lb(1,n,x)<<'\n';
        }
        else if (task==2)
        {
            fout<<ub(1,n,x)<<'\n';
        }
        
        
    }
}