#include<stdio.h>
using namespace std;
int n,m;
int a[100002];

int cb0(int x)
{
	int p,u,m;
	p=1;
	u=n;
	while(p<=u)
	{
		m=(p+u)/2;
		if(a[m]<=x)
			p=m+1;
		else
			u=m-1;
	}
	m=(p+u)/2;
	if(a[m]>x)
		--m;
	if(a[m]==x)
		return m;
	return -1;
}

int cb1(int x)
{
	int p,u,m;
	p=1;
	u=n;
	while(p<u)
	{
		m=(p+u)/2;
		if(a[m]<=x)
			p=m+1;
		else
			u=m;
	}
	m=(p+u)/2;
	if(a[m]>x)
		--m;
	return m;
}

int cb2(int x)
{
	int p,u,m;
	p=1;
	u=n;
	while(p<u)
	{
		m=(p+u)/2;
		if(a[m]<x)
			p=m+1;
		else
			u=m;
	}
	m=(p+u)/2;
	if(a[m]<x)
		++m;
	return m;
}

int main()
{
	int i,cod,x;
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;++i)
		scanf("%d",&a[i]);
	scanf("%d",&m);
	for(i=1;i<=m;++i)
	{
		scanf("%d %d",&cod,&x);
		if(cod==0)
			printf("%d\n",cb0(x));
		if(cod==1)
			printf("%d\n",cb1(x));
		if(cod==2)
			printf("%d\n",cb2(x));
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}