// http://infoarena.ro/problema/cautbin
#include <fstream>
#include <vector>
using namespace std;

#define maxSize 100001
int toBeFound;
vector<int> content;

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

int firstSearch(int left,int right);
int secondSearch(int left,int right);
int thirdSearch(int left,int right);

int main() {
	int lenght,number,type;

	in >> lenght;
	for(int i=1;i<=lenght;i++) {
		in >> number;
		content.push_back(number);
	}

	in >> number;	// numarul de interogari
	for(int i=1;i<=number;i++) {
		in >> type >> toBeFound;

		switch(type) {
			case 0: out << firstSearch(1,content.size()) << "\n"; break;
			case 1: out << secondSearch(1,content.size()) << "\n"; break;
			case 2: out << thirdSearch(1,content.size()); break;
		}
	}

	return (0);
}

int firstSearch(int left,int right) {
	if(left > right)
		return -1;
	else {
		int middle = (left + right) / 2;

		if(content[middle] == toBeFound) {
			while(content[middle] == toBeFound)
				middle++;

			return (middle);	// middle - 1 + 1
			// -1 din cauza ca in while a trecut de pozitia in care este egal cu toBeFound
			// +1 din cauza ca vectorul incepe cu pozitia 0
		}
		else
			if(content[middle] > toBeFound)
				return firstSearch(left,middle-1);
			else
				return firstSearch(middle+1,right);
	}
}

int secondSearch(int left,int right) {
	int middle  = (left + right) / 2;

	if(content[middle] <= toBeFound)
		if(content[middle+1] <= toBeFound)
			return secondSearch(middle+1,right);
		else
			return middle+1;	// +1 din cauza ca vectorul incepe cu pozitia 0
	else
		secondSearch(left,middle-1);
}

int thirdSearch(int left,int right) {
	int middle = (left + right) / 2;

	if(content[middle] >= toBeFound)
		if(content[middle-1] >= toBeFound)
			return thirdSearch(left,middle-1);
		else
			return middle+1;	// +1 din cauza ca vectorul incepe cu pozitia 0
	else
		thirdSearch(middle+1,right);
}