#include <fstream>
#include <vector>
#include <iostream>


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

int c_bin(std::vector<int>&v, int elem, int start, int stop){
	if(start >= stop && v[start] != elem){
		return -1;
	}

	int m = start + (stop - start) / 2;
	if (v[m] == elem){
		return m;
	}
	if(v[m] < elem){
		return c_bin(v, elem, m + 1, stop);
	}
	return c_bin(v, elem, start, m - 1);

}

int main(){

	int n, i, elem, m, opt;
	std::vector<int> v;

	fin >> n;
	for(i = 0; i < n; i++){
		int x;
		fin >> x;
		v.push_back(x);
	}

	fin >> m;

	for(i = 0; i < m; i++){
		fin >> opt >> elem;
		int poz = c_bin(v, elem, 0, n - 1);
		if(opt == 0){
			if(poz == -1){
				fout << "-1\n";
			}else{
				while(poz <= n - 1 && v[poz] == elem){
					poz ++;
				}
				fout << poz << '\n';
			}
		}
		if(opt == 1){
			while((poz = c_bin(v, elem, 0, n-1)) == -1){
				elem --;
			}
			while(poz <= n - 1 && v[poz] == elem){
				poz ++;
			}
			fout << poz << '\n';
		}
		if(opt == 2){
			while((poz = c_bin(v, elem, 0, n-1)) == -1){
				elem ++;
			}
			while(poz <= n - 1 && v[poz] == elem){
				poz --;
			}
			fout << poz + 2 << '\n';
		}
	}

	return 0;
}