#include<stdio.h>
int n,a[100001],m,min;
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,max=0;
	while(i<=j){
		mij=(i+j)/2;
		if(a[mij]<=x){
			if(max<mij)
			max=mij;
			i=mij+1;
		}
		else 
			j=mij-1;
	}
	return max;
}

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

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

		}
		else 
			i=mij+1;
	}
	return max;
}


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;
}