#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
using namespace std;
FILE *in = fopen("cautbin.in", "r");
int v[100001], n, m;

int cb0(int inf, int sup, int key)
{
	int m;
	while (inf <= sup){
		m = inf + (sup - inf) / 2;
		if (v[m] == key) break;
		else if (v[m] < key)
			inf = m + 1;
		else if (v[m] > key)
			sup = m - 1;
	}
	
	if (inf > sup) return -1;
	else{
		while (key == v[m])
			m++;
		return m-1;
	}

}
int cb1(int inf, int sup, int key)
{

	int m;
	while (inf < sup){

		m = inf + (sup - inf) / 2;
		if (v[m] <=key)
			inf = m + 1;
		else
			sup = m;
	}

	while (v[m] > key)
		m--;
	return m;
}
int cb2(int inf, int sup, int key)
{
	int m;
	while (inf < sup){
		m = inf + (sup - inf) / 2;
		if (v[m] < key)
			inf = m + 1;
		else
			sup = m;
	}
	while (v[m] < key)
		m++;
	return m;
}
int main()
{
	int i,val,tip;
	fscanf(in, "%d", &n);
	for (i = 1; i <= n; i++)
		fscanf(in, "%d", v + i);
	fscanf(in, "%d", &m);
	for (i = 0; i < m; i++){
		fscanf(in, "%d %d", &tip, &val);
		if (tip == 0) printf("%d\n", cb0(1, n, val));
		else if (tip == 1) printf("%d\n", cb1(1, n, val));
		else if (tip == 2) printf("%d\n", cb2(1, n, val));
	}

	return 0;
}
/*const int modulo = 666013;
int m[2][2] = { { 0, 1 }, { 1, 1 } }, sol[2][2] = { { 1, 0 }, { 0, 1 } },aux[2][2],n;
FILE *f = fopen("kfib.in", "r");
void inmultire(int m1[2][2], int m2[2][2], int m3[2][2])
{
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 2; k++)
				m3[i][j] = (m3[i][j] + 1ll*m1[i][k] * m2[k][j]) % modulo;

}
void rid_put_log(int put)
{
	int i;
	for (i = 0; (1 << i) <= put; i++){
		if (put & (1 << i)){
			memset(aux, 0, sizeof(aux));
			inmultire(sol, m, aux);
			memcpy(sol, aux, sizeof(aux));
		}
		memset(aux, 0, sizeof(aux));
		inmultire(m, m, aux);
		memcpy(m, aux, sizeof(aux));
	}
}
int main()
{
	fscanf(f, "%d", &n);
	rid_put_log(n-1);
	printf("%d ",sol[1][1]);
	return 0;
}
*/
/*FILE *f = fopen("spectacole.in", "r");
int n, t;
struct spectacol{
	int x, y, durata;
};
spectacol v[101];
void qsortare(int inf, int sup)
{
	int i, j, x;
	spectacol t;
	i = inf;
	j = sup;
	x = v[(i + j) / 2].y;
	do{

		while (i < sup && v[i].y < x) i++;
		while (j > inf && v[j].y>x) j--;
		if (i <= j){
			t = v[i];
			v[i] = v[j];
			v[j] = t;
			i++;
			j--;
		}
	} while (i <= j);
	if (i < sup) qsortare(i, sup);
	if (j > inf) qsortare(inf, j);
}
int main()
{
	int i, j,k;
	fscanf(f, "%d", &n);
	for (k = 0; k < n; k++){
		fscanf(f, "%d %d", &i, &j);
		v[k].x = i;
		v[k].y = j;
		v[k].durata = j - i;
	}

	qsortare(0, n);
	j = 1;
	int nr = 1;
	for (i = 2; i <= n; i++){
		if (v[i].x >= v[j].y){
			nr++;
			j = i;
		}
	}
	f = fopen("spectacole.out", "w");
	fprintf(f,"%d", nr);
	return 0;
}*/
/*FILE *f = fopen("bete2.in", "r"), *g = fopen("bete2.out", "w");
int v[3001], n;
int cb(int nr)
{
	int inf = 0, sup = n - 1;
	while (inf <= sup){

		int m = (inf + sup) / 2;
		if (v[m] == nr) return m;
		else if (nr < v[m]) sup = m - 1;
		else inf = m + 1;
	}

	return -1;
}
int main()
{
	int nr = 0;
	fscanf(f, "%d", &n);
	for (int i = 0; i < n; i++)
		fscanf(f, "%d", v + i);

	sort(v, v + n);

	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
		{
			int s = v[i] + v[j];
			int ok = cb(s);
			if (ok != -1) nr++;

		}

	fprintf(g,"%d", nr);
	fclose(g);

	return 0;
}*/