#include<stdio.h>
int n,i,v[100010],t,x,m;
int cb(int x,int &inc, int &sf)
{
	int med;
	while(inc<=sf)
	{
		med=(inc+sf)/2;
		if(v[med]==x)return med;
		else if(v[med]<x)
			inc=med+1;
		else sf=med-1;
	}
	return -1;
}
int cbf(int x)
{
	int a=1,b=n;
	int cbv=cb(x,a,b);
	if(cbv==-1)return -1;
	else while(v[cbv]==x)cbv++;
	return cbv-1;
}
int cbs(int x)
{
	int a=1,b=n;
	int cbv;
	cbv=cb(x,a,b);
	if(cbv==-1)return a;
	else while(v[cbv]==x)cbv++;
	return cbv-1;
}
int cbj(int x)
{
	int a=1,b=n;
	int cbv;
	cbv=cb(x,a,b);
	if(cbv==-1)return b;
	else while(v[cbv]==x)cbv--;
	return cbv+1;
}
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",&m);
	for(int q=1;q<=m;q++)
	{
		scanf("%d %d",&t,&x);
		if(t==0)printf("%d\n",cbf(x));
		if(t==1)printf("%d\n",cbs(x));
		if(t==2)printf("%d\n",cbj(x));
	}
	return 0;
}