#include <cstdio>

FILE*f=fopen("cautbin.in","r");
FILE*g=fopen("cautbin.out","w");

int N,sir[100001],M;

inline int cb0(int x){
	int low=1, last,mid,high=N;
	
	while(low<=high){
		mid=low+(high-low)/2;
		if(sir[mid]>=x){
			if(sir[mid]==x) last=mid;
			low=mid+1;
		}
		else{
			high=mid-1;
		}
	}
	return last;
}

inline int cb1(int x){
	int low=1,high=N,last,mid;

	while(low<=high){
		mid=low+(high-low)/2;
		if(sir[mid]<=x){
			last=mid;
			low=mid+1;
		}
		else high=mid-1;
	}
	return last;
}

inline int cb2(int x){
	int low=1,high=N,last,mid;
	
	while(low<=high){
		mid=low+(high-low)/2;
		if(sir[mid]>=x){
			last=mid;
			high=mid-1;
		}
		else low=mid+1;
	}
	return last;
}

int main(){
	fscanf(f,"%d",&N);
	for(int i=1;i<=N;i++){
		fscanf(f,"%d",&sir[i]);
	}
	fscanf(f,"%d",&M);
	int tip,x;
	for(;M;M--){
		fscanf(f,"%d %d",&tip,&x);
		
		if(!tip){
			fprintf(g,"%d\n",cb0(x));
		}
		else if(tip==1){
			fprintf(g,"%d\n",cb1(x));
		}
		else fprintf(g,"%d\n",cb2(x));
		
	}
	
	fclose(f);
	fclose(g);
	return 0;
}