#include<fstream>
using namespace std;
int v[100010];
int cautbin1(int p,int u,int val){
	int m;
	while(p<=u) m=(p+u)>>1,(v[m]<=val)?p=m+1:u=m-1;
	m=(p+u)>>1;
	if(v[m]>val) m--;
	if(v[m]==val) return m;
	return -1;
}
int cautbin2(int p,int u,int val){
	int m;
	while(p<u) m=(p+u)>>1,(v[m]<=val)?p=m+1:u=m;
	m=(p+u)>>1;
	if(v[m]>val) m--;
	return m;
}
int cautbin3(int p,int u,int val){
	int m;
	while(p<u) m=(p+u)>>1,(v[m]<val)?p=m+1:u=m;
	m=(p+u)>>1;
	if(v[m]<val) m++;
	return m;
}


ifstream f("cautbin.in");
ofstream g("cautbin.out");
int main(){
	int n,x,op,val;
	f>>n;
	for(int i=1;i<=n;++i) f>>v[i];
	f>>x;
	while(x--){
		f>>op>>val;
		if(op==0) g<<cautbin1(1,n,val)<<endl;
		if(op==1) g<<cautbin2(1,n,val)<<endl;
		if(op==2) g<<cautbin3(1,n,val)<<endl;
	}

	return 0;
}