#include <bits/stdc++.h>

using namespace std;

int n, v[100005],m;

int Cautbin0(int x)
{
    int mij, st, dr , pmax;
    dr=n;
    st=1;
    pmax = -1;
    while(st<=dr)
    {
        mij= (st+dr)/2;
        if(x == v[mij])
        {
            pmax=mij;
            st=mij+1;
        }
        if( x < v[mij]) dr=mij-1;
        if( x > v[mij]) st=mij+1;
    }
    return pmax;
}

int Cautbin1(int x)
{
    int mij, dr, st , pmax;
    st= 1;
    dr= n;
    while(st<=dr)
    {
        mij= (st+dr)/2;
        if( x >= v[mij])
        {
            pmax=mij;
            st=mij+1;
        }
        else dr=mij-1;
    }
    return pmax;
}

int Cautbin2(int x)
{
    int mij, dr, st, pmin;
    st= 1;
    dr= n;
    while( st<=dr)
    {
        mij= (st+dr)/2;
        if( x <= v[mij])
        {
            pmin=mij;
            dr=mij-1;
        }
        else st=mij+1;
    }
    return pmin;
}

int main()
{
    ofstream fout ("cautbin.out");
    int tip , x;
    ifstream fin("cautbin.in");
    fin>>n;
    for(int i = 1 ; i <= n ; i++)
        fin >> v[i] ;
    fin >> m ;
    for( int i = 1 ; i <= m ; i++)
    {
         fin>>tip >> x;
         if(tip == 0) fout<<Cautbin0(x)<<"\n";
         if(tip == 1) fout<<Cautbin1(x)<<"\n";
         if(tip == 2) fout<<Cautbin2(x)<<"\n";
    }
    return 0;
}