#include <cstdio>

using namespace std;

int n,m,v[100002];

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

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

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

int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	
	int op,x;
	
	scanf("%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",&op);
		scanf("%d",&x);
		if(op==0)
			printf("%d\n",op0(1,n,x));
		else if(op==1)
			printf("%d\n",op1(1,n,x));
		else 
			printf("%d\n",op2(1,n,x));
	}
}