#include <stdio.h>
#include <assert.h>




int N, M, v[100005];



inline int BS1(int x)
{
	int lo, hi, mijl;

	for (lo = 1, hi = N; lo <= hi; )
	{
		mijl = lo + (hi-lo) / 2;
		if (x < v[mijl]) hi = mijl-1;
		else if (v[mijl] < x) lo = mijl+1;
		else return mijl;
	}
	return -1;
}




inline int BS2(int x)
{
	int lo, hi, mijl, last = 0;

	for (lo = 1, hi = N; lo <= hi; )
	{
		mijl = lo + (hi-lo) / 2;
		if (v[mijl] <= x) last = mijl, lo = mijl+1;
		else hi = mijl-1;
	}
	return last;
}

inline int BS3(int x)
{
	int lo, hi, mijl, last = N+1;

	for (lo = 1, hi = N; lo <= hi; )
	{
		mijl = lo + (hi-lo) / 2;
		if (x <= v[mijl]) last = mijl, hi = mijl-1;
		else lo = mijl+1;
	}
	return last;
}



int main(void)
{
	int i, t, x;
	
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);

	scanf("%d", &N);	
	for (i = 1; i <= N; ++i)
		scanf("%d", &v[i]);
        
	scanf("%d", &M);
	for (; M; --M)
	{
		scanf("%d %d", &t, &x);
		if (!t)
			printf("%d\n", BS1(x));
		else if (t == 1)
			printf("%d\n", BS2(x));
		else
			printf("%d\n", BS3(x));
	}
}