#include <iostream>
#include <fstream>

using namespace std;

int N,M;
int elem[100000];

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


int main(){

	int i,j;
	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;
		out << bin_search(0, N-1, t, q) + 1 << endl;

		/*
		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;
}