#include<fstream>
using namespace std;

int v[100001],n,i,m,opt,x;

ifstream in("cautbin.in");
ofstream out("cautbin.out");
int cautare0(int x)
{
	int a=1,b=n,mij=(a+b)/2;
	while(a<=b)
	{
		if(v[mij]<=x)
			a=mij+1;
		else
			b=mij-1;
		mij=(a+b)/2;
	}
	if(v[mij]>x)
		mij--;
	if(v[mij]==x)
		return mij;
	else
		return -1;
}
int cautare1(int x)
{
	int a=1,b=n,mij=(a+b)/2;
	while(a<b)
	{
		if(v[mij]<=x)
			a=mij+1;
		else
			b=mij;
		mij=(a+b)/2;
	}
	if(v[mij]>x)
		mij--;
	return mij;
}
int cautare2(int x)
{
	int a=1,b=n,mij=(a+b)/2;
	while(a<b)
	{
		if(v[mij]<x)
			a=mij+1;
		else
			b=mij;
		mij=(a+b)/2;
	}
	if(v[mij]>x)
		mij+1;
	return mij;
}
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&opt,&x);
		
		if(opt==0)
			printf("%d\n",cautare0(x));
		else
			if(opt==1)
				printf("%d\n",cautare1(x));

			else
				printf("%d\n",cautare2(x));
	}
	
	return 0;
}