#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,max;
	while(i<j){
		mij=(i+j)/2;
		if(a[mij]==x){
			while(a[mij]==x)
				mij++;
			return mij-1;
		}
		if(a[mij]<x){
			max=mij;
			i=mij;
		}
		else 
			j=mij;
	}
	return max;
}

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

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

		}
		else 
			i=mij;
	}
	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;
}