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

	//out << "content size" << content.size() << " ";

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

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

	return (0);
}

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

		if(content[middle] == toBeFound)
			// daca nu este ultimul element si exista acelasi element pe urmatoarea pozitie
			if(middle != right && content[middle+1] == toBeFound)
				return firstSearch(middle+1,right);
			else
				return middle+1;
		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(middle != right && content[middle+1] <= toBeFound)
			return secondSearch(middle+1,right);
		else
			return middle+1;
	else
		if(content[middle] > toBeFound)
			return secondSearch(left,middle-1);
		else
			return secondSearch(middle+1,right);
}

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

	if(content[middle] >= toBeFound)
		if(middle != left && content[middle-1] >= toBeFound)
			return thirdSearch(left,middle-1);
		else
			return middle+1;
	else
		if(content[middle] > toBeFound)
			return thirdSearch(left,middle-1);
		else
			return thirdSearch(middle+1,right);
}