#include<stdio.h>

long n,m,t,x,k,a[100005],p=-10;

int main()
{	freopen("cautbin.in","r",stdin);
	scanf("%ld",&n);
	for(int i=1;i<=n;i++)
		scanf("%ld",&a[i]);
	scanf("%ld",&m);
	freopen("cautbin.out","w",stdout);
	long i,j,mid,ok;
	while(m>0)
	{	m--;
		scanf("%ld%ld",&t,&x);
		if(t==0)
		{	ok=0;
			for(i=1,j=n;i<=j && ok==0;)
			{	mid=i+(j-i)/2;
				if(a[mid]>x) j=mid-1;
				else if(a[mid]<x) i=mid+1;
				else ok=1;
			}
			if(ok==0) printf("-1\n");
			else printf("%ld\n",mid);
		}
		if(t==1)
		{	ok=0;
			for(i=1,j=n;i<=j;)
			{	mid=i+(j-i)/2;
				if(a[mid]<=x)
				{ 	i=mid+1;
					ok=mid;
				}
				else j=mid-1;
			}
			printf("%ld\n",ok);
		}
		if(t==2)
		{	ok=n+1;
			for(i=1,j=n;i<=j;)
			{	mid=i+(j-i)/2;
				if(a[mid]>=x)
				{ 	j=mid-1;
					ok=mid;
				}
				else i=mid+1;
			}
			printf("%ld\n",ok);
		}
	//	printf("%ld\n",k);
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
	
}