#include <stdio.h>

int cauta1(int v[], int x, int start, int stop)
{
	int mid, better;
	if ( start > stop )
		return -1;
	mid = start + ( stop - start ) / 2;
	if ( v[mid] == x )
	{
		better = cauta1(v, x, mid+1, stop);
		if ( better > mid )
			return better;
		else
			return mid;
	}
	if ( v[mid] < x )
		return cauta1(v, x, mid+1, stop);
	return cauta1(v, x, start, mid-1);
}

int cauta2(int v[], int x, int start, int stop)
{
	int mid;
	mid = start + ( stop - start ) / 2;
	if ( v[mid] <= x && v[mid+1] > x )
		return mid;
	if ( v[mid] > x )
		return cauta2(v, x, start, mid-1);
	return cauta2(v, x, mid+1, stop);
}

int cauta3(int v[], int x, int start, int stop)
{
	int mid;
	mid = start + ( stop - start ) / 2;
	if ( v[mid] >= x && v[mid-1] < x )
		return mid;
	if ( v[mid] >= x )
		return cauta3(v, x, start, mid-1);
	return cauta3(v, x, mid+1, stop);
}

int main()
{
	int v[100000], i, n, x, q, nr;
	freopen("cautabin.in", "r", stdin);
	freopen("cautabin.out", "w", stdout);
	scanf("%d", &n);
	for ( i = 0; i <= n - 1; i ++ )
		scanf("%d", &v[i]);
	
	scanf("%d", &q);
	for ( i = 1; i <= q; i++ )
	{
		scanf("%d%d", &nr, &x);
		if ( nr == 0 )
			printf("%d\n", cauta1(v, x, 0, n-1) + 1);
		if ( nr == 1 )
			printf("%d\n", cauta2(v, x, 0, n-1) + 1);
		if ( nr == 2 )
			printf("%d\n", cauta3(v, x, 0, n-1) + 1);
	}
	
}