#include <fstream>

using namespace std;

int sir[100000],ls,m,v,N;

int binary_search1(int val){
	int beg=0,end=N,mdl;
	while(beg<=end){
		mdl=(beg+end)/2;
		if(sir[mdl]==val){
			while(sir[mdl+1]==val)
				mdl++;
			return mdl+1;
		}else if(val<sir[mdl]){
			end=mdl-1;
		}else{
			beg=mdl+1;
		}
	}
	
}
int binary_search2(int val){
	int beg=0,end=N,mdl;
	while(beg<=end){
		mdl=(beg+end)/2;
		if(sir[mdl]==val){
			while(sir[mdl+1]==val)
				mdl++;
			return mdl+1;
		}else if(val<sir[mdl]){
			end=mdl-1;
		}else{
			beg=mdl+1;
		}
	}
	for(int i=beg;i>=0;i--){
		if(sir[i]<=val){
			return i+1;
		}
	}
}
int binary_search3(int val){
	int beg=0,end=N,mdl;
	while(beg<=end){
		mdl=(beg+end)/2;
		if(sir[mdl]==val){
			while(sir[mdl-1]==val)
				mdl--;
			return mdl+1;
		}else if(val<sir[mdl]){
			end=mdl-1;
		}else{
			beg=mdl+1;
		}
	}
	for(int i=0;i<N;i++){
		if(sir[i]>=val){
			return i+1;
		}
	}
}
int main(){
	int M,x,op;
	fstream fin("cautbin.in",ios::in);
	fstream fout("cautbin.out",ios::out);
	fin>>N;
	for(int i=0;i<N;i++){
		fin>>sir[i];
	}
	fin>>M;
	for(int i=0;i<M;i++){
		fin>>op>>x;
		m=op;
		if(op==0){
			fout<<binary_search1(x);
		}else if(op==1){
			fout<<binary_search2(x);
		}else if(op==2){
			fout<<binary_search3(x);
		}
		fout<<endl;
	}
	fin.close();
	fout.close();
	return 0;
}