#include<stdio.h>


int cauta0(int x,int n, int v[100001])
{
	int stanga,dreapta;
	stanga=1; dreapta=n;
	while(stanga<=dreapta)
	{
		int m=(stanga+dreapta)/2;
		if(v[m]<=x) stanga=m+1;
		else dreapta=m-1;
	}
	stanga--;
	if(v[stanga]!=x) stanga--;
	if(v[stanga]==x) return stanga;
	return -1;
}

int cauta1(int x,int n, int v[100001])
{
	int stanga,dreapta;
	stanga=1; dreapta=n;
	while(stanga<=dreapta)
	{
		int m=(stanga+dreapta)/2;
		if(v[m]<=x) stanga=m+1;
		else dreapta=m-1;
	}
	stanga--;
	if(v[stanga]>x) stanga--;
	return stanga;
}


int cauta2(int x,int n, int v[100001])
{
	int stanga,dreapta;
	stanga=1; dreapta=n;
	while(stanga<=dreapta)
	{
		int m=(stanga+dreapta)/2;
		if(v[m]<x) stanga=m+1;
		else dreapta=m-1;
	}
	dreapta++;
	if(v[dreapta]<x) dreapta++;
	return dreapta;
}


int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	int n,m,v[100001],intrebare,x;
	scanf("%d",&n);
	//printf("%d",n);
	for(int i=1; i<=n; ++i)
		scanf("%d",&v[i]);
	scanf("%d",&m);
	for(int i=1; i<=m; ++i)
		{
			scanf("%d %d",&intrebare,&x);
			if(!intrebare) printf("%d\n", cauta0(x,n,v));
			else if(intrebare==1) printf("%d\n", cauta1(x,n,v));
			else printf("%d\n", cauta2(x,n,v));
		}
	return 0;
}