#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 binarySearch_aux(int, 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, n, orderedElements, command);
		index += (index == -1) ? 0 : 1;
		outdata << index << "\n";
	}
	
	outdata.close();
	indata.close();
	return 0;
}

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