#include<stdio.h>
#define NMAX 100002
int v[ NMAX ], n, m, i, t, x, P;
int t0(int x, int F, int L, int p)
{
	int M;
	if(F <= L)
	{
	M = (L + F) / 2;
	if(v[M] > x)
		return t0(x, F, M-1, p);
	else if(v[M] < x)
		return t0(x, M+1, L, p);
	
	if(M > p)
		p = M;
	return t0(x, M+1, L, p);
	}
	return p;
}
int t1(int x, int F, int L, int p)
{
	int M;
	if(F <= L)
	{
	M = (L + F) / 2;
	if(v[M] <= x && M > p)
		p = M;
	if(v[M] <= x)
		return t1(x, M+1, L, p);
	return t1(x, F, M-1, p);
	}
	return p;
}
int t2(int x, int F, int L, int p)
{
	int M;
	if(F <= L)
	{
	M = (L + F) / 2;
	if(v[M] >= x && M < p)
		p = M;
	if(v[M] < x)
		return t2(x, M+1, L, p);
	return t2(x, F, M-1, p);
	}
	return p;
}
int main()
{
	FILE *f = fopen("cautbin.in", "r");
	FILE *g = fopen("cautbin.out", "w");
	fscanf(f, "%d", &n);
	for(i = 1; i <= n; i++)
		fscanf(f, "%d", &v[i]);
	fscanf(f, "%d", &m);
	for(i = 1; i <= m; i++)
	{
		fscanf(f, "%d %d", &t, &x);
		if(!t)
			P = t0(x, 1, n, -1);
		else if(t == 1)
			P = t1(x, 1, n, 0);
		else
			P = t2(x, 1, n, n);
		fprintf(g, "%d\n", P);
	}
	fclose(f);
	fclose(g);
	return 0;
}