#include <fstream>
#include <algorithm>

using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int N, M, A[100010],x,nr,poz;
bool u;
int main(){
	cin >> N;
	for(int i = 1; i <= N; i++)
		cin >> A[i];
	cin >> M;
	for(int i = 1; i <= M; i++){
		cin >> x;
		cin >> nr;
		if(x == 0){
			u = binary_search(A+1, A+N+1, nr);
			if(u){
				poz = upper_bound(A+1, A+N+1, nr) - A;
				cout << poz-1 << '\n';
			}else cout << "-1\n";
		}else if(x == 1){
			poz = upper_bound(A+1, A+N+1, nr) - A;
			cout << poz-1 << '\n';
		}else{
			poz = lower_bound(A+1, A+N+1, nr) - A;
			cout << poz << '\n';
		}
		}
	return 0;
}