#include<fstream>
#define nmax 100005
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,m,a[nmax],x,s,d;
int bin1()
{
	s=1;
	d=n;
	while(s<d)
	{
		int mid=(s+d)/2;
		if(x<a[mid])
			d=mid-1;
		else
			s=mid+1;
	}
	if(a[s]==x)
		return s;
	if(a[s-1]==x)
		return s-1;
	return -1;
}
int bin2()
{
	s=1;
	d=n;
	while(s<d)
	{
		int mid=(s+d)/2;
		if(x<a[mid])
			d=mid;
		else
			s=mid+1;
	}
	if(a[s]<=x)
		return s;
	return s-1;
}
int bin3()
{
	s=1;
	d=n;
	while(s<d)
	{
		int mid=(s+d)/2;
		if(x<=a[mid])
			d=mid;
		else
			s=mid+1;
	}
	if(a[s]>=x)
		return s;
	return s+1;
}
int main()
{
	f>>n;
	for(int i=1;i<=n;i++)
		f>>a[i];
	f>>m;
	while(m--)
	{
		f>>x;
		switch(x)
		{
			case 0:
				{
					f>>x;
					g<<bin1()<<'\n';
					break;
				}
			case 1:
				{
					f>>x;
					g<<bin2()<<'\n';
					break;
				}
			case 2:
				{
					f>>x;
					g<<bin3()<<'\n';
					break;
				}
		}
	}
	f.close();
	g.close();
	return 0;
}