#include<fstream>
using namespace std;

int main(){

	ifstream fin("cautbin.in");
	ofstream fout("cautbin.out");
	
	int n, a[100000], r=-2, aux, st, dr, i, j, x, m;
	fin >> n;
	for(i=0; i<n; i++){
		fin >> a[i];
	}
	fin >> m;
	for(i=0; i<m; i++){
		st = 0;
		dr = n-1;
		r=-2;
		fin >> j >> x;
		if(j == 0){
			while(st<dr){
				aux = (st + dr)/2;
				if(x >= a[aux]) {
					r = aux;
					st = aux + 1;
				}
				else dr = aux;
			}
			if(st == dr && a[st]==x) r = st;
			fout << r+1 << endl;
		}
		else if(j == 1){
			while(st<dr){
				aux = (st + dr)/2;
				if(x >= a[aux]){
				r = aux;
				st = aux+1;
				}
				else dr= aux;
			}
			if(st == dr && a[st]==x) r = st;
			fout << r+1 << endl;
		}
		if(j == 2){
			while(st < dr){
				aux = (st + dr)/2;
				if(x <= a[aux]){
					r = aux;
					dr = aux;
				}
				else st = aux+1;
			}
			if(st == dr && x==a[aux]) r = st;
			fout << r+1 << endl;
		}
	}
	
	fin.close();
	fout.close();

	return 0;
}