#include <cstdio>
int v[100001], n, c, x;
inline int bs( )
{
    int st=1, dr=n, med;
    if( c==0 )
    {
        while( st<=dr )
        {
            med=(dr-st)/2;
            if( v[med]<x )
                st=med;
            else if( v[med]>x )
                dr=med;
            else
                break;
        }
        while( v[med]==x && med<=n )
            med++;
        printf( "%d\n", med-1 );
    }
    else
    if( c==1 )
    {
        while( st<=dr )
        {
            med=(dr-st)/2;
            if( v[med]>x )
                dr=med;
            else
                break;
        }
        while( v[med]<=x )
            med++;
        printf( "%d\n", med-1 );
    }
    else
    {
        while( st<=dr )
        {
            med=(dr-st)/2;
            if( v[med]<x )
                st=med;
            else
                break;
        }
        while( v[med]>=x )
            med--;
        printf( "%d\n", med+1 );
    }
}
int main()
{
    freopen( "cautbin.in", "r", stdin );
    freopen( "cautbin.out", "w", stdout );
    int m, i;
    scanf( "%d", &n );
    for( i=1; i<=n; i++ )
        scanf( "%d", &v[i] );
    scanf( "%d", &m );
    for( i=1; i<=m; i++ )
        scanf( "%d%d", &c, &x ), bs();
    return 0;
}