#include <stdio.h>

#define NMAX 100005


int N, M, a[NMAX], t;


int BS0( int x)
{

	int st, dr, m;

	for ( st = 1, dr = N; st <= dr; )
	{
		m = st + (dr - st) / 2;
		if ( x < a[m] )
			dr = m - 1;
		else

		if ( x > a[m] )
			st = m + 1;
		else

			return m;
	}

	return -1;
}


int BS1(int x)
{

	int st, dr, m, u;

	for ( st = 1, dr = N; st <= dr; )
	{
		m = st + (dr - st) / 2;
		if ( a[m] <= x)
		{
			u = m;
			st = m + 1;
		}
		else

			dr = m - 1;
	}

	return u;
}


int BS2(int x)
{

	int st, dr, m, u;

	for ( st = 1, dr = N; st <= dr; )
	{
		m = st + (dr - st) / 2;
		if ( x <= a[m] )
		{
			u = m;
			dr = m - 1;
		}
		else

			st = m + 1;
	}

	return u;
}


int main()
{
	int i, x;

	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);

	scanf("%d", &N);
	for ( i = 1; i <= N; i++)
		scanf("%d", &a[i]);

	scanf("%d", &M);
	for ( i = 1; i <= M; i++)
	{
		scanf("%d %d", &t, &x);

		if ( t == 0)
			printf("%d\n", BS0(x) );
		else
		if ( t == 1)
			printf("%d\n", BS1(x) );
		else
			printf("%d\n", BS2(x) );


	}

	return 0;
}