# include <cstdio>
	using namespace std;
	
	int t, x, n, tip, i;
	int a[ 100001 ];
	
	int binsearch0 ( int x ) {
		int i, cnt = 1 << 20;
		for ( i = 1; cnt; cnt >>= 1 ) {
			if ( i + cnt <= n ) {
				if ( a[ i + cnt ] <= x ) i += cnt;
			}
		}
		if ( a[ i ] == x ) return i;
		return -1;
	}
	
	int binsearch1 ( int x ) {
		int i, cnt = 1 << 20;
		for ( i = 1; cnt; cnt >>= 1 ) {
			if ( i + cnt <= n ) {
				if ( a[ i + cnt ] <= x ) i += cnt;
			}
		}
		return i;
	}
	
	int binsearch2 ( int x ) {
		int st = 1, dr = n, mij;
		while ( st <= dr ) {
			mij = ( st + dr ) >> 1;
			if ( a[ mij ] == x ) dr = mij - 1;
			if ( a[ mij ] < x ) st = mij + 1;
			if ( a[ mij ] > x ) dr = mij - 1;
		}
		if ( a[ mij ] < x ) return mij + 1;
		return mij;
	}
	
	int main () {
		
		freopen ( "cautbin.in", "rt", stdin );
		freopen ( "cautbin.out", "wt", stdout );
		
		scanf ( "%d", &n );
		
		for ( i = 1; i <= n; ++i ) {
			scanf ( "%d", &a[ i ] );
		}
		
		for ( scanf ( "%d", &t ); t; --t ) {
			
			scanf ( "%d%d", &tip, &x );
			
			if ( tip == 0 ) printf ( "%d\n", binsearch0 ( x ) );
			if ( tip == 1 ) printf ( "%d\n", binsearch1 ( x ) );
			if ( tip == 2 ) printf ( "%d\n", binsearch2 ( x ) );
			
		}
		
		
		return 0;
	}