#include <stdio.h>
#include <stdlib.h>
//#define N 100010

int w,n,i;
int v[100010],val,x;

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

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

int cautb2 (int p, int u, int val)
{
	int m;
	while(p<u)
	{
		m=(p+u)/2;
		if(v[m]<val) p=m+1;
			else u=m;
	}
	m=(p+u)/2;
	if(v[m]<val) 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", &v[i]);
	scanf("%d", &w);
	while(w--)
	{
		scanf("%d %d", &x, &val);
		if(x==0) printf("%d\n", cautb (1,n,val));
		if(x==1) printf("%d\n", cautb1 (1,n,val));
		if(x==2) printf("%d\n", cautb2 (1,n,val));
	}
	return 0;
}