#include <algorithm>
#include <fstream>
using namespace std;

ifstream fi( "cautbin.in" );
ofstream fo( "cautbin.out" );

int n, m, i, type, x;
int a[ 100000 ];

int main()
{ 
    fi >> n;
    for( i = 1; i <= n; i++ ) 
        fi >> a[ i ];
    
    fi >> m;
    int nr, x, bin;
    for( i = 1; i <= m; i++ ) {
        fi >> type >> x;
        if( type == 0 ) 
            if( ( bin = binary_search( a + 1, a + n + 1, x ) ) ) 
                fo << ( upper_bound( a + 1, a + n + 1, x ) - a - 1 ) << '\n'; 
            else fo << "-1\n";
        else if( type == 1 ) 
            fo << ( upper_bound( a + 1, a + n + 1, x ) - a - 1 ) << '\n';
        else if( type == 2 ) 
            fo << ( lower_bound( a + 1, a + n + 1, x ) - a ) << '\n';
    }

    return 0;
}