#include<stdio.h>
#define N 100100
int v[N],n;
int cautbin(int x, int test){
	int m;
    int p=1;
	int q=n;
	while(p!=q){
		m=p+(q-p)/2;
		if(x<=v[m])
			q=m;
		else
			p=m+1;
	}
	if(test==0){
		if(x!=v[p])
			return -1;
		else return p;
	}
	if(test==1){
		if(x==v[p])
		return p;
		else return p-1;
		
	}
	if(test==2){
		//if(x==v[p])
			return p;
		//else return p+1
	}
}


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