#include <fstream>
using namespace std;

ifstream fi("cautbin.in");
ofstream fo("cautbin.out");

long i,j,n,m,p,x,a[1000001];

long b0(){
	long s=1,d=n,m;
	while (s<d){
		m=(s+d+1)/2;
		if (a[m]<=x) s=m; else d=m-1; 
	}
	if (a[s]==x) return s; else return -1;
}

long b1(){
	long s=1,d=n,m;
	while (s<d){
		m=(s+d+1)/2;
		if (a[m]<=x) s=m; else d=m-1; 
	}
	return s;
}

long b2(){
	long s=1,d=n,m;
	while (s<d){
		m=(s+d)/2;
		if (a[m]>=x) d=m; else s=m+1;
	}
	return s;
}

int main(){
	
	fi >> n;
	for (i=1; i<=n; i++) fi >> a[i];
	
	fi >> m;
	for (i=1; i<=m; i++){
		fi >> p >> x;
		switch (p){
			case 0: fo << b0() << "\n"; break;
			case 1: fo << b1() << "\n"; break;
			case 2: fo << b2() << "\n"; break;
		}
	}
	
	
	
	return 0;
}