#include<stdio.h>
long f[100001];
long a,b,k,i,n,x;
long bs1(long b)
{
		long st=1,dr=n,last=-1,med;
		while(st<=dr)
			{
				med=(st+dr)/2;
				if(f[med]<=b)
					{
					last=med;	
					st=med+1;
					}
				else
					dr=med-1;
			}
		return last;
}






long bs3(long b)
{
		long st=1,dr=n,last,med;
		while(st<=dr)
			{
				med=(st+dr)/2;
				if(f[med]>=b)
					{
					last=med;	
					dr=med-1;
					}
				else
					st=med+1;
			}
		return last;
}




int main()
{
		freopen("cautbin.in","r",stdin);
		freopen("cautbin.out","w",stdout);
		scanf("%ld",&n);
		for(i=1;i<=n;++i)
			scanf("%ld",&f[i]);
		scanf("%ld",&k);
		for(i=1;i<=k;++i)
			{
			scanf("%ld%ld",&a,&b);
			if(a==0)
				{
					x=bs1(b);
					if(f[x]!=b)
						printf("-1\n");
					else
						printf("%ld\n",bs1(b));
				}	
			else
				if(a==1)
					printf("%ld\n",bs1(b));
				else
					printf("%ld\n",bs3(b));
			}
		return 0;
}