#include <fstream>

using namespace std;

int n, v[100000], m;

int solve(int t, int x){
	int start = 0, end = n-1, poz = -1;
	while(start <= end){
		int mid = (start + end)/2;
		if(v[mid] < x){ 
			if(mid+1 <= end && v[mid+1] >= x && t==1) return mid;
			start = mid+1; continue; 
		}
		if(v[mid] > x){ 
			if(mid-1 >= start && v[mid-1] <= x && t==2) return mid;
			end = mid-1; continue; 
		}
		poz = mid;
		if(t == 0){ start = mid+1; }
		if(t == 1){ start = mid+1; }
		if(t == 2){ end = mid-1; }
	}
	return poz;
}

int main(){
	ifstream f("cautbin.in");
	f >> n;
	for(int i=0; i<n; i++) f >> v[i];
	
	ofstream g("cautbin.out");
	
	int t, x;
	f >> m;
	for(int i=0; i<m; i++){
		f >> t >> x;
		g << solve(t, x) << endl;
	}
	
	f.close();
	g.close();
	
	return 0;
}