#include <fstream>
#include <iostream>
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 && a[pos + step] <= x)
				pos += step;
			if(intr == 1 && a[pos + step] <= x)
				pos += step;
			if(intr == 2 && a[pos + step] < x)
				pos += step; 
		}
		   
	if(intr == 0) {
		if(pos != -1 &&  a[pos] == x)
			return pos + 1;
		else
			return -1;
	}
	if(intr == 1)
		return pos + 1;
	return pos + 2;
}