#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 aprox_c_bin(int v[], int elem, int start, int stop){
	if(start >= stop && v[start] != elem){
		return start;
	}

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

}

int main(){

	int n, i, elem, m, opt;
	int v[100000];

	fin >> n;
	for(i = 0; i < n; i++){
		fin >> v[i];
	}

	fin >> m;

	int poz;

	for(i = 0; i < m; i++){
		fin >> opt >> elem;

		if(opt == 0){
			poz = aprox_c_bin(v, elem, 0, n - 1);
			if(v[poz] != elem){
				fout << "-1\n";
			}else{
				while(poz <= n - 1 && v[poz] == elem){
					poz ++;
				}
				fout << poz << '\n';
			}
		}
		if(opt == 1){
			poz = aprox_c_bin(v, elem, 0, n-1);
			if(v[poz] != elem){
				int new_elem = v[poz];
				while(poz <= n - 1 && v[poz] == new_elem){
					poz ++;
				}
				fout << poz << '\n';
			}else{
				while(poz <= n - 1 && v[poz] == elem){
					poz ++;
				}
				fout << poz << '\n';
			}
		}
		if(opt == 2){
			poz = aprox_c_bin(v, elem, 0, n-1);
			if(v[poz] != elem){
				int new_elem = v[poz];
				while(poz > 0 && v[poz] == new_elem){
					poz --;
				}
				fout << poz + 1 << '\n';
			}else{
				while(poz >= 0 && v[poz] == elem){
					poz --;
				}
				fout << poz + 2<< '\n';
			}
		}
	}

	return 0;
}