#include<stdio.h>
#include<stdlib.h>
using namespace std;
int v[100005];
int cautare_bin1(int st,int dr,int x)
{
	int mij;
	while(st<=dr)
		{
			mij=(st+dr)/2;
			if(v[mij]<=x)
				st=mij+1;
			else
				dr=mij-1;
	}
	mij=(st+dr)/2;
	if(v[mij]>x)
		--mij;
	if(v[mij]==x)
		return mij;
	return -1;
}
int cautare_bin2(int st,int dr,int x)
{
	int mij;
	while(st<dr)
	{
		mij=st+(dr-st)/2;
		if(v[mij]<=x)
			st=mij+1;
		else
			dr=mij;
	}
	mij=st+(dr-st)/2;
	if(v[mij]>x)
		--mij;
	return mij;
}
int cautare_bin3(int st,int dr,int x)
{
	int mij;
	while(st<dr)
	{
		mij=st+(dr-st)/2;
		if(v[mij]<x)
			st=mij+1;
		else
			dr=mij;
	}
	mij=st+(dr-st)/2;
	if(v[mij]<x)
		++mij;
	return mij;
}
int main()
{
	int i,n,m,val,x;
	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",&val,&x);
		switch(val)
		{
		case 0:
			printf("%d\n",cautare_bin1(1,n,x));
			break;
		case 1:
			printf("%d\n",cautare_bin2(1,n,x));
			break;
		case 2:
			printf("%d\n",cautare_bin3(1,n,x));
			break;
		}
	}
	exit(0);
}