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