#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"), *out = fopen("cautbin.out", "w");
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) fprintf(out,"%d\n", cb0(1, n, val));
		else if (tip == 1) fprintf(out,"%d\n", cb1(1, n, val));
		else if (tip == 2) fprintf(out,"%d\n", cb2(1, n, val));
	}
	fclose(out);
	return 0;
}