#include<iostream>
#include<cstdio>
using namespace std;
int t,i,n,x,y,a[100001];
int caut1(int l)
{
	int st=1,dr=n,m;
	while(st<=dr)
	{
		m=(st+dr)/2;
		if(a[m]<=l)
			st=m+1;
		else
			dr=m-1;
	}
	m=(st+dr)/2;
	if(a[m]>l) m--;
	if(a[m]==l) return m;
	else return -1;
}
int caut2(int l)
{
	int st=1,dr=n,m;
	while(st<dr)
	{
		m=(st+dr)/2;
		if(a[m]<=l)
			st=m+1;
		else
			dr=m;
	}
	m=(st+dr)/2;
	if(a[m]>l)
		m--;
	return m;
}
int caut3(int l)
{
	int st=1,dr=n,m;
	while(st<dr)
	{
		m=(st+dr)/2;
		if(a[m]<l)
			st=m+1;
		else
			dr=m;
	}
	m=(st+dr)/2;
	if(a[m]<l)
		m++;
	return m;
}
int main()
{
	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",&t);
	while(t--)
	{
		scanf("%d%d",&x,&y);
		if(x==0)
			printf("%d\n",caut1(y));
		else
		if(x==1)
			printf("%d\n",caut2(y));
		else
			printf("%d\n",caut3(y));
	}
	return 0;
}