#include<stdio.h>
int n,a[100001],m,min,max;
void citire(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	scanf("%d",&m);
}

int query1(int i,int j,int x){
	int mij;
	while(i<j){
		mij=(i+j)/2;
		if(a[mij]<=x){
			i=mij+1;
		}
		else 
			j=mij-1;
	}
	mij=(i+j)/2;
	if(a[mij]>x) 
		--mij;
	return mij;
}

int query0(int i,int j,int x){
	int mij,max=-1;
	while(i<=j){
		mij=(i+j)/2;
		if(a[mij]==x){
			max=mij;
			i=mij+1;
		}
		if(a[mij]>x)
			j=mij-1;
		if(a[mij]<x)
			i=mij+1;
	}
	return max;
}

int query2(int i,int j,int x){
	int mij;
	while(i<j){
		mij=(i+j)/2;
		if(a[mij]>=x)
			j=mij-1;
		else 
			i=mij+1;
	}
	mij=(i+j)/2;
	if(a[mij]<x)
		++mij;
	return mij;
}


int main(){
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	citire();
	int x,q;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&q,&x);
		if(q==0)
			printf("%d\n",query0(1,n,x));
		else
			if(q==1)
				printf("%d\n",query1(1,n,x));
			else
				printf("%d\n",query2(1,n,x));
	}
	return 0;
}