#include <iostream>
#include <fstream>

using namespace std;

int N,M;
int elem[100000];

int bin_search(int left,int right,int x){
	int m = (left + right)/2;
	//Daca s-a gasit numarul
	if(elem[m] == x){
		//Daca este ultma aparitie
		if((m == N-1) || (elem[m+1] > elem[m])){
			return m;
		}
		//Cauta ultima aparitie
		else{
			return bin_search(m + 1, right,x);
		}
	}
	else if(left >= right){
		return -1;
	}
	else if(elem[m] < x){
		return bin_search(m + 1, right, x);
	}

	return bin_search(left, m -1, x);
}
int bin_search2(int left,int right,int x){
	int m = (left + right)/2;
	//Daca s-a gasit numarul
	if(elem[m] <= x && ((m == N-1) || (elem[m+1] > x))){
		return m;
	}
	//Daca nu este cea mai mare aparitie
	else if(elem[m] == x){
		return bin_search2(m + 1, right, x);
	}
	else if(left >= right){
		return -1;
	}
	else if(elem[m] < x){
		return bin_search2(m + 1, right, x);
	}

	return bin_search2(left, m - 1, x);
}
int bin_search3(int left,int right,int x){
	int m = (left + right)/2;
	//Daca s-a gasit numarul
	if(elem[m] >= x && ((m == 0)||(elem[m-1] < x))){
		return m;
	}
	//Daca nu este cea mai mare aparitie
	else if(elem[m] == x){
		return bin_search3(left, m - 1, x);
	}
	else if(left >= right){
		return -1;
	}
	else if(elem[m] < x){
		return bin_search3(m + 1, right, x);
	}

	return bin_search3(left, m - 1, x);
}

int main(){

	int i;
	int q,t;

	ifstream in("cautbin.in");
	ofstream out("cautbin.out");

	in >> N;
	for(i = 0; i < N; i++)
		in >> elem[i];
	in >> M;
	for(i = 0 ; i < M; i++){
		in >> q >> t;
		switch (q) {
			case 0:
				out << bin_search(0, N-1, t) + 1 << endl;
			break;
			case 1:
				out << bin_search2(0, N-1, t) + 1 << endl;
			break;
			case 2:
				out << bin_search3(0, N-1, t) + 1 << endl;
			break;
		}
	}


	in.close();
	out.close();
	return 0;
}