#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 - 1, n, elements, option);
}
int binarySearch_aux(int x, int lb, int ub, int n, int elements[], int option) {
	int middle = 0;
	//cout << x << endl;
	while(lb < ub) {
		//cout << lb << " " << ub << endl;
		middle = (lb + ub) / 2;
		if (elements[middle] < x) {
			lb = middle + 1;
		} else {
			ub = middle - 1;
		}
	}
	
	middle = (lb + ub) / 2;
	//cout << lb << " " << ub << " " << middle << " " << x << endl << endl;
	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;
			}
		}
	}
	
	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;
		}
	}	
}