#include<stdio.h>

int xx,q,a[100000],y,i,j,t,n,x;

int cautbin(int st,int dr,int m,int x)
{
	if (a[m]==x||st>=dr) return m;
	if (a[m]>x) return cautbin(st,m-1,(st+m-1)/2,x);
		else return cautbin(m+1,dr,(m+dr+1)/2,x);
}


int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%d",&a[i]);
	
	scanf("%d",&t);
	
	for (i=1;i<=t;i++)
		{
			scanf("%d%d",&xx,&y);
			q=cautbin(1,n,(n+1)/2,y);
			if (xx==0) 
			{
				if (a[q]!=y) 
					printf("-1\n");
					
				while (a[q]==y) q++;
				if (a[q-1]==y) printf("%d\n",q-1);
			}
			if (xx==1)
			{
				if (a[q]<=y) while (a[q]==a[q+1]) q++;
					else q--;
				printf("%d\n",q);
			}				
			if (xx==2)
			{
				if (a[q]>=y) while (a[q]==a[q-1]) q--;
					else q++;
				printf("%d\n",q);
			}
	}
	
	return 0;
}