#include <cstdio>
int a[1<<17]; 
int n;
int functie0(int b)
{
	int i,pas;
	for (pas=1;pas<=n;pas<<=1); // Puterea lui 2 <n
	for (i=0; pas!=0; pas>>=1)
		if (i+pas<=n &&  a[i+pas]<=b)
			i+=pas;
	if (a[i]!=b) return -1;
	return i;
}

int functie1(int b)
{
	int i,pas;
	for (pas=1;pas<=n;pas<<=1); // Puterea lui 2 <n
	for (i=0; pas!=0; pas>>=1)
		if (i+pas<=n &&  a[i+pas]<=b)
			i+=pas;
	return i;
}

int functie2(int b)
{
	b--;
	int i,pas;
	for (pas=1;pas<=n;pas<<=1); // Puterea lui 2 <n
	for (i=0; pas!=0; pas>>=1)
		if (i+pas<=n &&  a[i+pas]<=b)
			i+=pas;
	return i+1;
}

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