#include<stdio.h>
int nr[100010],n;
int caut(int x){
	int pr,ul,mij;
	for(pr=1,ul=n;pr<=ul;){
		mij=pr+(ul-pr)/2;
		if(nr[mij]>x)
			ul=mij-1;
		else{
			if(nr[mij]<x)
				pr=mij+1;
			else
				return mij;
		}
	}
	return -1;
}
int caut1(int x){
	int pr,ul,mij,a=1;
	for(pr=1,ul=n;pr<=ul;){
		mij=pr+(ul-pr)/2;
		if(nr[mij]<=x){
			a=mij;
			pr=mij+1;
		}
		else
			ul=mij-1;
	}
	return a;
}
int caut2(int x){
	int pr,ul,mij,a=1;
	for(pr=1,ul=n;pr<=ul;){
		mij=pr+(ul-pr)/2;
		if(nr[mij]>=x){
			a=mij;
			ul=mij-1;
		}
		else
			pr=mij+1;
	}
	return a;
}
int main(){
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	int m,i,x,y;
	scanf("%d",&n);
	for(i=1;i<=n;++i)
		scanf("%d",&nr[i]);
	scanf("%d",&m);
	for(i=0;i<m;++i){
		scanf("%d%d",&x,&y);
		if(!x)
			printf("%d\n",caut(y));
		if(x==1)
			printf("%d\n",caut1(y));
		if(x==2)
			printf("%d\n",caut2(y));
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}