#include <fstream>
#include <iostream>
using namespace std;
int n,a[100001];
int f0(int x){
	int st=1,dr=n;
	while(st<dr){
		int m = st+(dr-st)/2;
		if( a[m] == x && (m==n || a[m+1]!=x))
			return m;
		if(a[m]<=x)
			st = m+1;
		else
			dr= m-1;
	}
	return -1;
}
int f1(int x){
	int st=1,dr=n;
	while(st<=dr){
		int m = st+(dr-st)/2;
		//cout<<m;
		if(a[m]<=x && (m==n || a[m+1]!=x))
			return m;
		if(a[m]<=x)
			st= m+1;
		else
			dr = m-1;
	}
	return 0;
}
int f2(int x){
	int st=1,dr=n;
	while(st<=dr){
		int m =st+(dr-st)/2;
		if(a[m]>=x &&( m==1 || a[m-1]!=x))
			return m;
		if(a[m]>=x)
			dr = m-1;
		else
			st = m+1;

	}
	return 0;
}
int main(){
	ifstream fin("cautbin.in");
	fin>>n;
	for(int i=1;i<=n;i++)
		fin>>a[i];
	int m;
	fin>>m;
	ofstream fout("cautbin.out");
	for( ; m ; --m){
		int c,x;
		fin>>c>>x;
		switch(c){
			case 0:fout<<f0(x)<<endl;break;
			case 1:fout<<f1(x)<<endl;break;
			case 2:fout<<f2(x)<<endl;break;
		}
	}
	fout.close();
	return 0;
}