#include <stdio.h>

int caz1();
int caz2();
int caz3();

int a[100001],n,m,x,nr;
FILE *f=fopen("cautbin.in","r"),*g=fopen("cautbin.out","w");

int main()
{
	int i;
	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",&x,&nr);
			if(x==0)
				fprintf(g,"%d\n",caz1());
			else
				if(x==1)
					fprintf(g,"%d\n",caz2());
				else
					if(x==2)
						fprintf(g,"%d\n",caz3());
		}
    return 0;
}

int caz1()
{
	int st=1,dr=n,mid;
	while(st<=dr)
		{
			mid=(st+dr)/2;
			if(nr<a[mid])
				dr=mid-1;
			else
				if(nr>a[mid])
					st=mid+1;
				else
					return mid;
		}
	return -1;
}
int caz2()
{
	int st=1,dr=n,mid,poz=0;
	while(st<=dr)
		{
			mid=(st+dr)/2;
			if(nr>=a[mid])
				{
					poz=mid;
					st=mid+1;
				}
			else
				dr=mid-1;
		}
	return poz;
}
int caz3()
{
	int st=1,dr=n,mid,poz=0;
	while(st<=dr)
		{
			mid=(st+dr)/2;
			if(nr<=a[mid])
				{
					dr=mid-1;
					poz=mid;
				}
			else
				st=mid+1;
		}
	return poz;
}