#include<fstream>
using namespace std;
int n, i, m, p, u, mid, t, x;
int v[100001];
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int main(){
	fin>> n;
	for(i = 1; i <= n; i++){
		fin>> v[i];
	}
	fin>> m;
	for(i = 1; i <= m; i++){
		fin>> t >> x;
		p = 1;
		u = n;
		if(t == 0){
			while(p <= u){
				mid = (p + u) / 2;
				if(v[mid] <= x){
					p = mid + 1;
				}
				else{
					u = mid - 1;
				}
			}
			if(v[u] == x){
				fout<< u <<"\n";
			}
			else{
				fout<< -1 <<"\n";
			}
		}
		if(t == 1){
			while(p <= u){
				mid = (p + u) / 2;
				if(v[mid] <= x){
					p = mid + 1;
				}
				else{
					u = mid - 1;
				}
			}
			if(v[u] == x){
				fout<< u <<"\n";
			}
			else{
				fout<< u -1 <<"\n";
			}
		}
		if(t == 2){
			while(p <= u){
				mid = (p + u) / 2;
				if(v[mid] < x){
					p = mid + 1;
				}
				else{
					u = mid - 1;
				}
			}
			if(v[p] == x){
				fout<< p <<"\n";
			}
			else{
				fout<< p - 1 <<"\n";
			}
		}
	}
	return 0;
}