#include<fstream>
using namespace std;

#define MAX 100010

ifstream in("cautbin.in");
ofstream out("cautbin.out");

int v[MAX];
int N,M,op,el;

int cautbin_1(int x)
{
	int l=1,r=N,mid;
	int max=-1;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(v[mid]==x)
		{
			max=mid;
			l=mid+1;
		}
		else if(v[mid] > x)
			r=mid-1;
		else
			l=mid+1;
	}
	return max;
}

int cautbin_2(int x)
{
    int l=1,r=N,mid;
	int max=0;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(v[mid]<=x)
		{
			max=mid;
			l=mid+1;
		}
		else if(v[mid] > x)
			r=mid-1;
	}
	return max;
}

int cautbin_3(int x)
{
    int l=1,r=N,mid;
	int min=0XFFFFFFFF;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(v[mid]>=x)
		{
			min=mid;
			r=mid-1;
		}
		else
			l=mid+1;
	}
	
    return min;
}

int main()
{

	in>>N;

	for(int i=1;i<=N;i++)
		in>>v[i];
	in>>M;

	for(int i=1;i<=M;i++)
	{
		in>>op;
		in>>el;

		if(op==0)
		{
		    out<<cautbin_1(el)<<endl;
		}
		else if(op==1)
		{
		   out<<cautbin_2(el)<<'\n';
		}
		else if(op==2)
		{
		   out<<cautbin_3(el)<<'\n';
		}

	}

	in.close();
	out.close();
	return 0;
}