#include <cstdio>
using namespace std;

int n,a[100001],m,x,p;

int caut0(int val);
int caut1(int val);
int caut2(int val);

int main(){
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;++i){
		scanf("%d%d",&p,&x);
		if (p==0) printf("%d\n",caut0(x));
		if (p==1) printf("%d\n",caut1(x));
		if (p==2) printf("%d\n",caut2(x));
		}
	
	return 0;
}

int caut2(int val){
	int i,step;
	for(step=1;step<n;step<<=1);
	for(i=0;step;step>>=1)
		if(i+step<n&&a[step+i]<val)
			i+=step;
	return i+1;
}

int caut1(int val){
	int i,step;
	for(step=1;step<n;step<<=1);
	for(i=0;step;step>>=1)
		if(i+step<n&&a[step+i]<=val)
			i+=step;
	if (a[i+1]<=val) return i+1;
	else return i;
}

int caut0(int val){
	int i,step;
	for(step=1;step<n;step<<=1);
	for(i=0;step;step>>=1)
		if(i+step<n&&a[step+i]<=val)
			i+=step;
	if (a[i]==val) return i;
	else return -1;
}