#include <bits/stdc++.h>

using namespace std;

const int NMAX = 100005;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int N, M;
int V[NMAX];
int t, x;

int BinSearch( int lf, int rg, int val )
{
    if( lf > rg ) return -1;

    int mid = lf + ( rg - lf )/2;

    //cout << mid << ' ' << V[mid] << '\n';
    if( val  == V[mid] ) return max( mid, BinSearch( mid+1, rg, val ) );

    if( val < V[mid] ) return BinSearch( lf, mid-1, val );
    if( val > V[mid] ) return BinSearch( mid+1, rg, val );
}

int UpperBound( int lf, int rg, int val )
{
    if( lf > rg ) return N+1;

    int mid = lf + ( rg - lf )/2;

    if( V[mid] >= val ) return min( mid, UpperBound( lf, mid-1, val ) );
    else return UpperBound( mid+1, rg, val );
}

int LowerBound( int lf, int rg, int val )
{
    if( lf > rg ) return 0;

    int mid = lf + ( rg - lf )/2;

    if( V[mid] <= val ) return max( mid, LowerBound( mid+1, rg, val ) );
    else return LowerBound( lf, mid-1, val );
}

void Solve()
{
    fin >> N ;
    for( int i = 1; i <= N; ++i )
        fin >> V[i];

    fin >> M;
    for( int i = 1; i <= M; ++i )
    {
        fin >> t >> x;
        if( t == 0 ) fout << BinSearch( 1, N, x ) << '\n';
        if( t == 2 ) fout << UpperBound( 1, N, x ) << '\n';
        if( t == 1 ) fout << LowerBound( 1, N, x ) << '\n';
    }
}
int main()
{
    Solve();
    return 0;
}