#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define in "cautbin.in"
#define out "cautbin.out"
#define NMAX 100005

int N, M;
int A[NMAX];

inline int BS1(int x)
{	
	int bl, bm, br;

	for ( bl = 1, br = N; bl <= br; )
	{
		bm = bl + ((br-bl)>>1);
		if ( x < A[bm] ) br = bm-1;
		else if ( x > A[bm] ) bl = bm+1;
		else return bm;
	}
	return -1;
}

inline int BS2(int x)
{
	int bl, bm, br, last = 0;
	for ( bl = 1, br = N; bl <= br; )
	{
		bm = bl + ((br-bl)>>1);
		if ( x >= A[bm] ) last = bm, bl = bm+1;
		else br = bm-1;
	}
	return last;
}

inline int BS3(int x)
{
	int bl, bm, br, last = N+1;
	for ( bl = 1, br = N; bl <= br; )
	{
		bm = bl + ((br-bl)>>1);
		if ( x <= A[bm] ) last = bm, br = bm-1;
		else bl = bm + 1;
	}
	return last;
}

int main( void )
{
	freopen ( in, "r", stdin );
	freopen ( out, "w", stdout );

	scanf ( "%d", &N );
	int i, op, X;

	for ( i = 1; i <= N; ++i )
		scanf ( "%d", (A+i) );
	scanf ( "%d", &M );

	for ( ; M; --M )
	{
		scanf ( "%d%d", &op, &X );
		if ( !op ) printf ( "%d\n", BS1(X) );
		else if ( op == 1 ) printf ( "%d\n", BS2(X) );
		else printf ( "%d\n", BS3(X) );
	}	
	
	return 0;
}