#include<fstream>
using namespace std;
int v[100010];
int cautbin1(int p,int u,int val){
	int m;
	while(p<=u) m=(p+u)>>1,(v[m]<=val)?p=m+1:u=m-1;
	m=(p+u)>>1;
	if(v[m]>val) m--;
	if(v[m]==val) return m;
	return -1;
}
int cautbin2(int p,int u,int val){
	int m;
	while(p<u) m=(p+u)>>1,(v[m]<=val)?p=m+1:u=m;
	m=(p+u)>>1;
	if(v[m]>val) m--;
	return m;
}
int cautbin3(int p,int u,int val){
	int m;
	while(p<u) m=(p+u)>>1,(v[m]<val)?p=m+1:u=m;
	m=(p+u)>>1;
	if(v[m]<val) m++;
	return m;
}


int main(){
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout); 
	int n,m,op,val;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&v[i]);
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&op,&val);
		if(op==0) {printf("%d\n",cautbin1(1,n,val));continue;}
		if(op==1) {printf("%d\n",cautbin2(1,n,val));continue;}
		printf("%d\n",cautbin3(1,n,val));
	}

	return 0;
}