#include <bits/stdc++.h>

using namespace std;

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

int n, m, cod, a[100100], x, ans;

int main(){
	in >> n;
	for(int i = 1; i <= n; i++) in >> a[i];
	in >> m;
	while(m--){
		in >> cod >> x;
		if(cod == 0){
			ans = upper_bound(a+1, a+n+1, x)-a-1;
			if(a[ans] == x) out << ans << '\n'; else out << "-1\n";
			cout << ans;
			continue;
		}
		if(cod == 1){
			out << lower_bound(a+1, a+n+1, x+1)-a-1 << '\n';
			continue;
		}
		out << upper_bound(a+1, a+n+1, x-1)-a << '\n';
	} 
	return 0;
}