#include <fstream>

using namespace std;

const char InFile[]="cautbin.in";
const char OutFile[]="cautbin.out";

int n,m,v[100002],tip,x;

int cautbin1(int x){
	int lo, hi, mid;

	for(lo=1,hi=n;lo<=hi;){
		mid=lo+(hi-lo)/2;
		if(x<v[mid]){
			hi=mid-1;
		}else if(v[mid]<x){
			lo=mid+1;
		}else{ 
			return mid;
		}
	}
	return -1;
}

int cautbin2(int x){
	int lo,hi,mid,last=0;

	for(lo=1,hi=n;lo<=hi;){
		mid=lo+(hi-lo)/2;
		if(v[mid]<=x){
			last=mid; 
			lo=mid+1;
		}
		else{
			hi=mid-1;
		}
	}
	return last;
}

int cautbin3(int x){
	int lo,hi,mid,last=n+1;

	for(lo=1,hi=n;lo<=hi;){
		mid=lo+(hi-lo)/2;
		if(x<=v[mid]){
			last=mid;
			hi=mid-1;
		}else{
			lo=mid+1;
		}
	}
	return last;
}

int main(void)
{
	
	ifstream fin(InFile);
	ofstream fout(OutFile);

	fin>>n;	
	for(register int i=1;i<=n;++i){
		fin>>v[i];
	}
        
	fin>>m;
	for(register int i=0;i<m;++i){
		fin>>tip>>x;
		if(tip==0){
			fout<<cautbin1(x)<<"\n";
		}else if(tip==1){
			fout<<cautbin2(x)<<"\n";
		}else{
			fout<<cautbin3(x)<<"\n";
		}
	}
	fout.close();
	fin.close();
}