#include <fstream.h>
#define MaxN 100009

int a[MaxN],n,m,t,x,i;

int caut0(int x)
{
	int st=1,dr=n,m,p;
	while(a[st]!=x && a[dr]!=x && st<dr-1) 
	{
		m=(st+dr)/2;
		if(a[m]>x)
			dr=m;
		else
			if(a[m]<=x)
				st=m;
	}
	if(a[st]==x)
		p=st;
	else
		if(a[dr]==x)
			p=dr;
		else
			p=0;
	while(a[p]==x)
		p++;
	p--;
	return p;
}

int caut1(int x)
{
	int st=1,dr=n,m,l=0;
	while(st<=dr)
	{
		m=st+(dr-st)/2;
		if(a[m]<=x)
		{
			l=m;
			st=m+1;
		}
		else
			dr=m-1;
	}
	return l;
}

int caut2(int x)
{
	int st=1,dr=n,m,l=n+1;
	while(st<=dr)
	{
		m=st+(dr-st)/2;
		if(x<=a[m])
		{
			l=m;
			dr=m-1;
		}			
		else
			st=m+1;  
	}
	return l;
}

int main()
{
	ifstream fin("cautbin.in");
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>a[i];
	fin>>m;
	ofstream fout("cautbin.out");
	for(i=1;i<=m;i++)
	{
		fin>>t>>x;
		switch(t){
		case 0:
			fout<<caut0(x)<<'\n';
			break;
		case 1:
			fout<<caut1(x)<<'\n';
			break;
		case 2:
			fout<<caut2(x)<<'\n';
			break;
		}
	}
	fin.close();
	fout.close();
	return 0;
}