#include <stdio.h>
#define MA 100001
using namespace std;
int n,m,A[MA],i;
int op,x;

FILE *f,*g;

int bs0(int x)
{
	int st=1,dr=n,mij;
	while (st<=dr)
	{
		mij=(st+dr)/2;
		if (A[mij]<=x)
			st=mij+1;
		else
			dr=mij-1;
	}
	if (A[(st+dr)/2]==x)
		return (st+dr)/2;
	else 
		return -1;
}

int bs1(int x)
{
	int st=1,dr=n,mij;
	while (st<dr)
	{
		mij=(st+dr)/2;
		if (A[mij]<=x)
			st=mij+1;
		else 
			dr=mij;
	}
	mij=(st+dr)/2;
	if (A[mij]>x)
		mij--;
	return mij;
}

int bs2(int x)
{
	int st=1,dr=n,mij;
	while (st<dr)
	{
		mij=(st+dr)/2;
		if (A[mij]<x)
			st=mij+1;
		else
			dr=mij;
	}
	return (st+dr)/2;
}

int main()
{
	f=fopen("cautbin.in","r");
	g=fopen("cautbin.out","w");
	fscanf(f,"%d",&n);
	for (i=1;i<=n;++i)
		fscanf(f,"%d ",&A[i]);
	fscanf(f,"%d",&m);
	for (i=1;i<=m;++i)
	{
		fscanf(f,"%d %d",&op,&x);
		if (op==0)
			fprintf(g,"%d \n",bs0(x));
		else if (op==1)
			fprintf(g,"%d \n",bs1(x));
		else if (op==2)
			fprintf(g,"%d \n",bs2(x));
	}
	fclose(f);
	fclose(g);
	return 0;
}