#include <stdio.h>

FILE *f=fopen("cautbin.in","r");
FILE *g=fopen("cautbin.out","w");

int q0(int k);
int q1(int k);
int q2(int k);
int k,n,a[100001],x,i,t;

int main()
{
	fscanf(f,"%d",&n);
	for(i=1;i<=n;i++)
		fscanf(f,"%d",&a[i]);
	fscanf(f,"%d",&k);

	for(i=1;i<=k;i++)
	{
		fscanf(f,"%d%d",&x,&t);
		if(x==0)
			fprintf(g,"%d\n",q0(t));
		else
			if(x==1)
				fprintf(g,"%d\n",q1(t));
			else
				fprintf(g,"%d\n",q2(t));
	}

	return 0;
}

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

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

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