#include <stdio.h>
#include <stdlib.h>
#define LL long long
LL n,nr,vec[110000],tip,num;

int comparator(const void* a1,const void* a2) {
	LL _a1 = (*(LL*)a1);
	LL _a2 = (*(LL*)a2);
	if(_a1 > _a2) return 1;
	if(_a1 ==_a2) return 0;
	return -1;
}

int main() {
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	
	scanf("%d",&n);
	for(int i = 0 ; i< n; i++)
		scanf("%lld",&vec[i]);
	scanf("%lld",&nr);
	
	for(int i = 1 ; i<=nr; nr++) {
		scanf("%lld %lld",&tip,&num);
		LL*addr = (LL*)bsearch( (void*)(&num),(void*)vec,n,sizeof(vec[0]),comparator);
		
		if(tip == 0) {
			LL poz = -1;
			if(addr == NULL)
				printf("-1\n");
			else {
				poz = addr - vec;
				while( (poz < n-1) && (vec[poz] == vec[poz+1]) )
					poz++;
				printf("%lld\n",poz+1);
			}
		}
		
		if(tip == 2) {
			LL poz = addr - vec;
			while(vec[poz] == vec[poz-1])
				poz--;
			poz--;
			printf("%lld\n",poz+1);
		}
		
		if(tip == 1) {
			LL poz = addr - vec;
			while(vec[poz] == vec[poz+1])
				poz++;
			poz++;
			printf("%lld\n",poz+1);
		}
			
	}
	
	return 0;
}