#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

unsigned long bin_search_0(unsigned long begin,unsigned long end,unsigned long *a,unsigned long x){
	while(end-begin>1){
		unsigned long pos=(begin+end)/2;
		if(a[pos]==x){
			while(a[pos+1]==x&&pos<end-1)
				pos++;
			return pos+1;
		}
		if(a[end-1]==x)
			return end;
		if(a[pos]>x)
			end=pos;
		else
			begin=pos;
	}
	return -1;
}
unsigned long bin_search_1(unsigned long begin,unsigned long end,unsigned long *a,unsigned long x){
	if(a[end-1]<=x)
		return end;
	unsigned long pos;
	while(end-begin>1){
		pos=(begin+end)/2;
		if(a[pos]>x)
			end=pos;
		else
			begin=pos;
		
	}
	while(a[pos+1]<=x&&pos<end-1)
		pos++;
	return pos;
}
unsigned long bin_search_2(unsigned long begin,unsigned long end,unsigned long *a,unsigned long x){
	if(a[0]>=x)
		return 0;
	unsigned long pos;
	while(end-begin>1){
		pos=(begin+end)/2;
		if(a[pos]>x)
			end=pos;
		else
			begin=pos;
	}
	while(a[pos-1]>=x&&pos>0)
		pos--;
	return pos+1;
}
int main(){
	//Files
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	//The array
	unsigned long *a,n;
	scanf("%lu",&n);
	a=(unsigned long*)malloc(sizeof(unsigned long)*n);
	for(unsigned long i=0;i<n;i++)
		scanf("%lu",&a[i]);
	//Questions
	unsigned long m,x;
	short question;
	scanf("%lu",&m);
	while(m--){
		scanf("%hd %lu",&question,&x);
		switch(question){
			case 0: printf("%lu\n", bin_search_0(0,n,a,x)); break;
			case 1: printf("%lu\n", bin_search_1(0,n,a,x)); break;
			case 2: printf("%lu\n", bin_search_2(0,n,a,x)); break;
		}
	}
	fclose(stdin);
	fclose(stdout);
    return 0;
}