#include<fstream>
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
	
int n, i, step, a[100000], x, j, val, m, sol;

int cautbin0(int val){
	for(step=1; step<=n; step<<=1);
		for(i=0; step; step>>=1) if(i+step <= n && a[i+step] <= val) i+=step;
	if(a[i] != val) sol = -1;
		else sol = i;
	fout << sol << "\n";
}

int cautbin1(int val){
	for(step=1; step<=n; step<<=1);
		for(i=0; step; step>>=1) if(i+step <= n && a[i+step] <= val) i+=step;
	sol = i;
	fout << sol << "\n";
}

int cautbin2(int val){
	for(step=1; step<n; step<<=1);
		for(i=n; step; step>>=1) if(i-step >= 0 && a[i-step]>= val) i-=step;
	sol = i;
	fout << sol << "\n";
}


int main(){
	
	fin >> n;
	for(j=1; j<=n; j++){
		fin >> a[j];
	}
	
	fin >> m;
	for(j=0; j<m; j++){
		fin >> x >> val;
		if(x == 0) cautbin0(val);
		else if(x == 1) cautbin1(val);
		else if(x == 2) cautbin2(val);
	}
	
	fin.close();
	fout.close();
	
	return 0;
}