#include <vector>
#include <fstream>
#include <cmath>
#include <utility>
using namespace std;

int lowest(const vector<int>& v, const int x){
	static const int num_biti = log2(v.size());
	int cur = (1<<(num_biti+1)) - 1;
	for(int i = 1<<(num_biti); i > 0; i /= 2){
		if((cur-i < v.size()) && v[cur-i] >= x){
			cur -= i; } }
	return min(cur, (decltype(cur))(v.size()-1)); }

int highest(const vector<int>& v, const int x){
	static const int num_biti = log2(v.size());
	int cur = 0;
	for(int i = 1<<(num_biti); i > 0; i /= 2){
		if((cur+i < v.size()) && v[cur + i] <= x){
			cur += i; } }
	return min(cur, (decltype(cur))(v.size()-1)); }

int main(){
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	int n = 0;
	f >> n;
	vector<int> v(n);
	for(auto& x : v){
		f >> x; }
	int m = 0;
	f >> m;
	for(int i = 0, a, b; i < m; ++i){
		f >> a >> b;
		if(a == 0){
			const int rez = highest(v, b);
			if(v[rez] != b){
				g << "-1\n"; }
			else{
				g << (rez+1) << '\n'; } }
		else if(a == 1){
			g << (highest(v, b)+1) << '\n'; }
		else{
			g << (lowest(v, b)+1) << '\n'; } }
	return 0; }