#include <iostream>
#include <fstream>
#define c 100001
using namespace std;

int task0(int n, int a[], int x) {
	int ls, ld, r = -1;
	ls = 1;
	ld = n;
	while (ls <= ld)  {
		if (x == a[(ls + ld)/2]) {
			r = (ls + ld)/2;

		}
		if (x >= a[(ls + ld)/2]) 
				ls = 1 + (ls + ld)/2;
		else 
			if (x <= a[(ls + ld)/2]) 
				ld = (ls + ld)/2 -1;
			
	}	
	return r;
}

int task1(int n, int a[], int x) {
	int ls, ld, poz, m;
	ls = 1;
	ld = n;
	while (ls <= ld)  {
		m = (ld + ls)/2;
		if (x >= a[m]) {
			ls = m + 1;
			poz = m;
		}
		else
			if (x <= a[m]) {
				ld = m -1;
			}
	}
	return poz ;

}

int task2(int n, int a[], int x) {
	int ls, ld, poz, m;
	ls = 1;
	ld = n;
	while (ls <= ld)  {
		
		m = (ls + ld)/2;
		if (x <= a[m]) {
			ld = m-1;
			poz = m;
		}
		else
			if (x >= a[m]) 
				ls = m +1 ;
	}	
	return poz ;

}

int main() {

int m, n, a[c], i, ok=0, ls, ld, r, nr, x;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
f >> n;
for (i = 1; i <= n; i++) {
	f >> a[i];
}
f >> m;
for (i=1; i <= m; i++) {
	f >> nr >> x;
	switch(nr) {
	case 0: 
		g << task0(n,a,x) << endl;
		break;
	case 1:
		g << task1(n,a,x) << endl;
		break;
	case 2:
		g << task2(n,a,x) << endl;
		break;
	}
}
	
f.close();
g.close();
return 0;
}