#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
 
#define pb push_back
#define INF 1000000

vector <int> A;
int N;

int bin0(int x)
{
	int lo,hi,mid,last = -1;
	for (lo = 1, hi = N; lo <= hi;)
	{
		mid = lo + (hi - lo) / 2;
		if (A[mid] > x)
			hi = mid - 1;
		else 
		{
			if (A[mid] == x)
				last = mid;
			lo = mid + 1;
		}
	}

	return last;
}

int bin1(int x)
{
	int lo,hi,mid,last;
	for (lo = 1, hi = N; lo <= hi;)
	{
		mid = lo + (hi - lo) / 2;
		if (A[mid] > x)
			hi = mid - 1;
		else
			last = mid, lo = mid + 1;
	}

	return last;
}

int bin2(int x)
{
	int lo,hi,mid,last;
	for (lo = 1, hi = N; lo <= hi;)
	{
		mid = lo + (hi - lo) / 2;
		if (A[mid] >= x)
			last = mid, hi = mid - 1;
		else
			lo = mid + 1;
	}

	return last;
}

int main()
{
	int i,M,a,x;
	char buf[100];
	long sum=0;

	freopen("cautbin.in", "rt", stdin);
//	freopen("cautbin.out", "wt", stdout);

	scanf("%d",&N);
//	printf("%d\n",N);

	A.pb(INF);

	for (i=0;i<N;i++)
	{
		scanf("%d",&a);
		A.pb(a);
	}

	scanf("%d",&M);

	for (i=0;i<M;i++)
	{
		scanf("%d %d",&a,&x);
//		printf("%d %d\n",a,x);
		switch(a)
		{
			case 0:
				printf("%d\n",bin0(x));
				break;
			case 1:
				printf("%d\n",bin1(x));
				break;
			case 2:
				printf("%d\n",bin2(x));
				break;
		}
	}

	return 0;
}