#include <fstream>
using namespace std;

int n;
int a[100000];

int binSrch(int, int);

int main(void) {
	ifstream fin("cautbin.in");
	fin >> n;
	for(int i = 0; i < n; ++i)
		fin >> a[i];
	
	ofstream fout("cautbin.out");
	int m, intr, x;
	fin >> m;
	for(int i = 0; i < m; ++i) {
		fin >> intr >> x;
		fout << binSrch(intr, x) << '\n';
	}
	fin.close();
	fout.close();
}

int binSrch(int intr, int x) {
	int step, pos;
	for(step = 1; step < n; step <<= 1) {}
	for(pos = - 1; step != 0; step >>= 1) 
		if(pos + step < n) {
			if((intr == 0 || intr == 1) && a[pos + step] <= x)
				pos += step;
			else if(a[pos + step] < x)
				pos += step;
		}
		   
	if(intr == 0 && (pos != -1 &&  a[pos] == x))
		return pos;
	else
		return -1;
	if(intr == 1)
		return pos;
	return pos + 1;
}