#include<fstream>
using namespace std;
int v[100005];
int cautbin0(int st, int dr,int x){
	int mij,rasp=0;
	while (st<=dr){
		mij=(st+dr)/2;
		if (v[mij]<=x){
			rasp=mij;
			st=mij+1;}
		else{ 
			dr=mij-1;}
	}
	if(v[rasp]==x)
		return rasp;
	else return -1;
}
int cautbin1(int st,int dr, int x){
	int mij,rasp;
	while (st<=dr){
		mij=(st+dr)/2;
	if(v[mij]<=x){
        rasp=mij;
		st=mij+1;}
	else{
		dr=mij-1;}
	}
	return rasp;
}
int cautbin2(int st,int dr, int x){
	int mij,rasp;
	while (st<=dr){
		mij=(st+dr)/2;
		if(v[mij]<x){
		st=mij+1;
	}
	else{
		rasp=mij;
		dr=mij-1;}
	}
	return rasp;
}
int main(){
	int i,n,m,tip,nr;
    ifstream in("cautbin.in"); 
	ofstream out("cautbin.out");
	in>>n;
	for(i=1;i<=n;i++){
		in>>v[i];
	}
	in>>m;
	while(m--){
		in>>tip>>nr;
		if(tip==0){
			out<<cautbin0(1,n,nr)<<endl;}
	    if(tip==1){
			out<<cautbin1(1,n,nr)<<endl;}
		if(tip==2){
			out<<cautbin2(1,n,nr)<<endl;}
	}
	return 0;
}