#include<stdio.h>

int v[100001];

int bins1(int x,int n)
{
	int st=1,dr=n,last=1,med;
	
	while(st<=dr)
	{
		med=st+(dr-st)/2;
		if(v[med]<=x)
			{
				last=med;
				st=med+1;
			}			
		else dr=med-1;
	}
	
	return last;
}

int bins2(int x,int n)
{
	int st=1,dr=n,last=1,med;
	
	while(st<=dr)
	{
		med=st+(dr-st)/2;
		if(v[med]>=x)
			{
				last=med;
				dr=med-1;
			}			
		else st=med+1;
	}
	
	return last;
}




int main()
{
	freopen("bs.in","r",stdin);
	freopen("bs.out","w",stdout);
	int q,x,poz;
	long n,m;
	
	scanf("%ld",&n);
	int i;
	for(i=1;i<=n;++i)
		scanf("%d",&v[i]);
	
	scanf("%ld",&m);
	for(i=1;i<=m;++i)
	{
		scanf("%d %d",&q,&x);
		switch(q)
		{
		case 0:{
				poz=bins1(x,n);
				if(v[poz]==x)
					printf("%d\n",poz);
				else printf("-1\n");
				break;
				}
		case 1:{
				printf("%d\n",bins1(x,n));
				break;
				}
		case 2:{
				printf("%d\n",bins2(x,n));
				break;
				}
		}
	}
	return 0;
}