#include<stdio.h>
long n,*a,m,x,y;
long cb1(long val)  
{
	long i,zero;  
	for(zero=1;zero<n;zero<<=1);  
	for(i=0;zero;zero>>=1)  
        	if(i+zero<=n && a[i+zero]<=val)  
           		i+=zero;
	return i;
}
long cb2(long val)  
{
	long i,zero;  
	for(zero=1;zero<n;zero<<=1);  
	for(i=n;zero;zero>>=1)  
        	if(i-zero>0 && a[i-zero]>=val)  
           		i-=zero;
	return i;
}
int main()
{
	long i;
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%ld",&n);
	a=new long[n];
	for(i=1;i<=n;++i)
		scanf("%ld",&a[i]);
	scanf("%ld",&m);
	for(;m;--m){
		scanf("%ld %ld",&x,&y);
		if(x==0)
			if(a[cb1(y)]==y){
				printf("%ld\n",cb1(y));
				continue;
			}
			else{
				printf("-1\n");
				continue;
			}
		if(x==1){
			printf("%ld\n",cb1(y));
			continue;
		}
		if(x==2){
			printf("%ld\n",cb2(y));
			continue;
		}
	}
	fcloseall();
	return 0;
}