#include <cstdio>
int a[1<<17];
int n,y,x;

int functie1 (int x)
{
	int i,pas;
	for (pas=1; pas<=n; pas<<=1);  // 2^n
	for (i=1; pas; pas>>=1)
		if (i+pas<=n && a[i+pas]<=x) i+=pas;
	return i;
}
int functie0 (int x)
{
	int i,pas;
	for (pas=1; pas<=n; pas<<=1);  // 2^n
	for (i=1;pas;pas>>=1)
		if (i+pas<=n && a[i+pas]<=x) i+=pas;
	if (a[i]!=x) return -1;
	return i;
}
int functie2 (int x)
{
	int i,pas;
	--x;
	for (pas=1;pas<=n;pas<<=1); // 2^n
	for (i=1;pas;pas>>=1)
		if (i+pas<=n && a[i+pas]<=x) i+=pas;
	return 1+i;
}

int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
    int i;
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d",&a[i]);
	int m;
	scanf("%d",&m);
	for (i=1;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		if (x==0) 
		{
			printf("%d\n",functie0(y));
		}
		else 
			if (x==1) 
			{
				printf("%d\n",functie1(y));
			}
			else
			{
				printf("%d\n",functie2(y));
			}
	}
	return 0;
}