#include <fstream>
#define N 100010

std::ifstream in ("cautbin.in");
std::ofstream out ("cautbin.out");

int a[N],n,m,k,x,i;

int bsearch1 (int l,int r) {
	if (r-l==1)
		if (a[l]==x) return l;
		else return -2;
	int m=(l+r)/2;
	if (a[m]<=x) return bsearch1 (m,r);
	return bsearch1 (l,m);
}

int bsearch2 (int l,int r) {
	if (r-l==1) return l;
	int m=(l+r)/2;
	if (a[m]<=x) return bsearch2 (m,r);
	return bsearch2 (l,m);
}

int bsearch3 (int l,int r) {
	if (r-l==1)
		if (a[l]>=x) return l;
		else return r;
	int m=(l+r)/2;
	if (a[m]>=x) return bsearch3 (l,m);
	return bsearch3 (m,r);
}

int main () {
	in>>n;
	for (i=0; i<n; i++) in>>a[i];
	in>>m;
	while (m--) {
		in>>k>>x;
		if (!k) out<<bsearch1 (0,n)+1<<"\n";
		else
			if (k==1) out<<bsearch2 (0,n)+1<<"\n";
			else out<<bsearch3 (0,n)+1<<"\n";

	}
	return 0;
}