#include <stdio.h>
#define N 100010
int a[N],n;
int x;
int y;
int cautare0(int st, int dr, int x)
{
	int mij;
	if (st <= dr)
	{
		mij = (st + dr)/2;
		if (a[mij] <= x)
			return cautare0(mij + 1 , dr , x);
		else
			return cautare0(st , mij - 1 , x);
	}
	mij = (st + dr)/2;
	if (a[mij] == x)
		return mij;
	return -1;
}
int cautare1(int st, int dr, int x)
{
	int mij;
	if (st < dr)
	{
		mij = (st + dr)/2;
		if (a[mij] <= x)
			return cautare1(mij + 1 , dr , x);
		else
			return cautare1(st , mij , x);
	}
	mij = (st + dr)/2;
	if (a[mij] > x)
		mij--;
	return mij;
}
int cautare2(int st, int dr, int x)
{
	int mij;
	if (st < dr)
	{
		mij = (st + dr)/2;
		if (a[mij] < x)
			return cautare2(mij + 1 , dr , x);
		else
			return cautare2(st , mij , x);
	}
	mij = (st + dr)/2;
	if (a[mij] < x)
		mij++;
	return mij;
}
int main()
{
	freopen ("cautbin.out","w",stdout);
	freopen ("cautbin.in","r",stdin);
	scanf ("%d",&n);
	for (int i = 1 ; i <= n ; ++i)
		scanf ("%d ",&a[i]);
	int nri;
	scanf("%d",&nri);
	for (int i = 0 ; i < nri ; ++i)
	{
		int in,x;
		scanf("%d %d\n",&in,&x);
		if (in == 0)
			printf("%d\n",cautare0(1,n,x));
		if (in == 1)
			printf("%d\n",cautare1(1,n,x));
		if (in == 2)
			printf("%d\n",cautare2(1,n,x));
	}
	return 0;
}