#include<stdio.h>
long n,i,m,f,x,last;
long v[100005];
int bs(long val)
{
	int st,dr,med;
	st=1;
	dr=n;
	last=-1;
	while(st<=dr)
	{
		med=st+(dr-st)/2;
		if(v[med]<=val)
		{
			last=med;
			st=med+1;
		}
		else
			dr=med-1;
	}
	return last;
}
int bs1(long val)
{
	int st,dr,med;
	st=1;
	dr=n;
	while(st<=dr)
	{
			med=st+(dr-st)/2;
			if(val>=v[med])
			{
				last=med;
				st=med+1;
			}
			else
				dr=med-1;
	}
	return last;
}
int bs2(long val)
{
	int st,dr,med;
	st=1;
	dr=n;
	while(st<=dr)
	{
		med=st+(dr-st)/2;
		if(val<=v[med])
		{
			last=med;
			dr=med-1;
		}
		else
			st=med+1;
	}
	return last;
}
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%ld",&n);
	int nr;
	for(i=1;i<=n;++i)
	{
		scanf("%ld",&v[i]);
	}
	scanf("%ld",&m);
	for(i=1;i<=m;++i)
	{
		scanf("%ld%ld",&f,&x);
		if(f==0)
		{
			nr=bs(x);
			printf("%d\n",nr);
		}
		if(f==1)
		{
			nr=bs1(x);
			printf("%d\n",nr);
		}
		if(f==2)
		{
			nr=bs2(x);
			printf("%d\n",nr);
		}
	}
	return 0;
}