#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

#define NMax 100010

int n, m;
int a[NMax];

int main(){
	int i, c, x;
	int *it;
	fin >> n;
	for(i = 0; i < n; i++) fin >> a[i];
	fin >> m;
	for(i = 0; i < m; i++){
		fin >> c >> x;
		if(c == 0){
			it = upper_bound(a, a + n, x);
			it--;
			if(*it == x) fout << it - a + 1;
			else fout << -1;
		}
		else if(c == 1){
			it = upper_bound(a, a + n, x);
			it--;
			fout << it - a + 1;
		}
		else{
			it = lower_bound(a, a + n, x);
			fout << it - a + 1;
		}
		fout << '\n';
	}
}