#include<iostream>
#include<fstream>
using namespace std;

#define MAX 100001

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

unsigned long v[MAX];
unsigned long N,M,op,el;

unsigned long cautbin_1(unsigned long x)
{
	unsigned long l=1,r=N,mid;
	unsigned long 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;
}

unsigned long cautbin_2(unsigned long x)
{
    unsigned long l=1,r=N,mid;
	unsigned long 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;
}

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

int main()
{

	in>>N;

	for(unsigned long i=1;i<=N;i++)
		in>>v[i];
	in>>M;
	for(unsigned long 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)<<endl;
		}
		else if(op==2)
		{
		   out<<cautbin_3(el)<<endl;
		}

	}

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