#include <stdio.h>

#define NMAX 100010


long a[NMAX];
long n, m;


long zero(long x)
{
	long st = 1, dr = n, m;

	while(st <= dr)
	{
		m = (st+dr) >> 1;

		if(a[m] < x)
			st = m+1;
		else if(a[m] > x)
			dr = m-1;
		else
			return m;
	}
	return -1;
}

long unu(long x)
{
	long st = 1, dr = n, m;

	while(st <= dr)
	{
		m = (st+dr) >> 1;

		if(a[m] == x)
			return m;
		else if(a[m] < x && a[m+1] > x)
			return m;

		else if(a[m] < x)
			st = m+1;
		else
			dr = m-1;
	}
	return m;
}

long doi(long x)
{
	long st = 1, dr = n, m;

	while(st <= dr)
	{
		m = (st+dr) >> 1;

		if(a[m] == x)
			return m;
		else if(a[m] > x && a[m-1] < x)
			return m;
		else if(a[m] > x)
			dr = m-1;
		else
			st = m+1;
	}
	return m;
}

int main()
{
	long i, o, x;
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);


	scanf("%ld", &n);
	for(i = 1; i <= n; ++i)
		scanf("%ld ", &a[i]);
	a[n+1] = 2000000000;

	scanf("%ld", &m);
	for(i = 1; i <= m; ++i)
	{
		scanf("%ld %ld", &o, &x);

		if(o == 0)
			printf("%ld\n", zero(x));
		else if(o == 1)
			printf("%ld\n", unu(x));
		else if(o == 2)
			printf("%ld\n", doi(x));
	}

	return 0;
}