#include <stdio.h>
#define N 100010
int a[N],n;
int cautare0(int st, int dr, int x)
{
	int mij;
	while (st <= dr)
	{
		mij = (st + dr)/2;
		if (a[mij] <= x)
			st = mij + 1;
		else
			dr = mij - 1;
	}
	mij = (st + dr)/2;
	if (a[mij] == x)
		return mij;
	return -1;
}
int cautare1(int st, int dr, int x)
{
	int mij;
	while (st < dr)
	{
		mij = (st + dr)/2;
		if (a[mij] <= x)
			st = mij + 1;
		else
			dr = mij;
	}
	mij = (st + dr)/2;
	if (a[mij] > x)
		mij--;
	return mij;
}
int cautare2(int st, int dr, int x)
{
	int mij;
	while (st < dr)
	{
		mij = (st + dr)/2;
		if (a[mij] < x)
			st = mij + 1;
		else
			dr = mij;
	}
	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;
}