#include <fstream>
#include <iostream>
using namespace std;

///// DESCRIPTION
// THIS PROGRAM FINDS ALL COMBINATIONS
// OF NUMBERS BETWEEN 1 AND n
// BY USING BACKTRACKING
/////

int binarySearch(int, int, int, int[], int);

int main(int argc, char **argv)
{
	// INPUT
	int n, m;
	
	ifstream indata("cautbin.in");
	
	indata >> n;
	int orderedElements[n];
	for (int i = 0; i < n; i++) {
		indata >> orderedElements[i];
	}
	
	// SEARCH AND OUTPUT
	ofstream outdata("cautbin.out");
	
	indata >> m;
	int command, x;
	for (int i = 0; i < m; i++) {
		indata >> command >> x;
		int index = binarySearch(x, 0, n, orderedElements, command) + 1; 	
		outdata << index << "\n";
	}
	
	outdata.close();
	indata.close();
	return 0;
}

int binarySearch(int x, int lb, int ub, int elements[], int option) {
	int middle = (lb + ub) / 2;
	if (elements[middle] == x) {
		switch(option) {
			case 0: {
				while(elements[++middle] == x);
				return middle - 1;
			}
			case 1: {
				while(elements[++middle] == x);
				return middle - 1;
			}
			case 2: {
				while(elements[--middle] == x);
				return middle + 1;
			}
		}
	} else if (lb == ub) {
		switch(option) {
			case 0: return -2;
			case 1: {
				if (elements[middle] > x) {
					return middle - 1;
				}
				return middle;
			}
			case 2: {
				if (elements[middle] < x) {
					return middle + 1;
				}
				return middle;
			}
		}
	}
	
	if (x > elements[middle]) {
		return binarySearch(x, middle + 1, ub, elements, option);
	}
	
	if (x < elements[middle]) {
		return binarySearch(x, 0, middle - 1, elements, option);
	}
}