#include <cstdio>

#define MAX 100000
int vec[MAX],n;

int search1(int v){
	int beg=0,end=n-1,mdl,f;
	while(beg<=end){
		mdl=beg+((end-beg)>>1);
		if(v==vec[mdl]){
			if(vec[mdl+1]!=v){
				return mdl;
			}else{
				beg=mdl+1;
			}
		}else if(v<vec[mdl]){
			end=mdl-1;
		}else{
			beg=mdl+1;
		}
	}
	return -2;
}
int search2(int v){
	int beg=0,end=n-1,mdl,last=0;
	while(beg<=end){
		mdl=beg+((end-beg)>>1);
		if(vec[mdl]<=v){
			last=mdl,beg=mdl+1;
		}else{
			end=mdl-1;
		}
	}
	return last;
}
int search3(int v){
	int beg=0,end=n-1,mdl,last=0;
	while(beg<=end){
		mdl=beg+((end-beg)>>1);
		if(vec[mdl]>=v){
			last=mdl,end=mdl-1;
		}else{
			beg=mdl+1;
		}
	}
	return last;
}
int main(){
	FILE* fin=fopen("cautbin.in","r");
	freopen("cautbin.out","w",stdout);
	int m,o,x;
	fscanf(fin,"%d",&n);
	for(int i=0;i<n;i++){
		fscanf(fin,"%d",&vec[i]);
	}
	fscanf(fin,"%d",&m);
	for(int i=0;i<m;i++){
		fscanf(fin,"%d %d",&o,&x);
		switch(o){
			case 0:
				printf("%d\n",search1(x)+1);
				break;
			case 1:
				printf("%d\n",search2(x)+1);
				break;
			case 2:
				printf("%d\n",search3(x)+1);
				break;
			default:
				continue;
		}			
	}
	fclose(fin);
	return 0;
}