#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");

int a[10010];

/*int bin(int lo, int hi){
	int piv = lo + (hi-lo)/2;
	if (lo == hi)
		return -1;
	if (piv == x)
		return x;
	if (piv > x)
		return (bin(lo, piv));
	if (piv < x)
		return (bin(piv,hi));
}*/

int bin0(int lo, int hi, int el){
	/*r = bin(0, n-1);
	while (bin(r+1, n-1)!=-1){
		r = bin(r+1, n-1);
	}*/
	int piv;
	while (lo <= hi){
		piv = (lo + hi) / 2;
		if (a[piv] <= el)
			lo = piv + 1;
		else
			hi = piv - 1;
	}
	piv = (lo + hi) / 2;
	if (a[piv] > el) piv--;
	if (a[piv] == el)
		return piv;
	return -1;
}

int bin1(int lo, int hi, int el){
	//r = bin(0, n-1);
	int piv, n = hi;
	while (lo < hi){
		piv = (lo + hi) / 2;
		if (a[piv] <= el)
			lo = piv + 1;
		else
			hi = piv;
	}
	piv = (lo + hi) / 2;
	if (a[piv] > el)
		--piv;
	return piv;
}

int bin2(int lo, int hi, int el){
	//r = bin(0, n-1);
	int piv;
	while (lo < hi){
		piv = (lo + hi) / 2;
		if (a[piv] < el)
			lo = piv + 1;
		else
			hi = piv;
	}
	piv = (lo + hi) / 2;
	if (a[piv] < el)
		++piv;
	return piv;
}

void cit(){
	int n, m, c, x;
	fin >> n;
	for (int i = 1; i <= n; i++){
		fin >> a[i]; 
	}
	fin >> m;
	for (int i = 0; i < m; i++){
		fin >> c >> x;
		if (c == 0)
			fout << bin0(1, n, x) << "\n";
		else if (c == 1)
			fout << bin1(1, n, x) << "\n";
		else if (c == 2)
			fout << bin2(1, n, x) << "\n";
	}
}

int main(){
	cit();
	return 0;
}