#include<stdio.h>
int n,i,m,v,va,poz,x[100001];
int bin2(int val)
{
	int st,dr,med,last=-1;
	st=1;dr=n;
	while(st<=dr)
	{
		med=st+(dr-st)/2;
		if(x[med]>=val)
		{	
			dr=med-1;
			last=med;
		}
		else
			st=med+1;
	}
	return last;
}
int bin(int val)
{
	int st,dr,med,last=-1;
	st=1;dr=n;
	while(st<=dr)
	{
		med=st+(dr-st)/2;
		if(x[med]<=val)
		{
			st=med+1;
			last=med;
		}
		else
			dr=med-1;
	}
	return last;
}
		
	
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);

	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&x[i]);
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&v,&va);
		switch (v)
		{
			case 0 : {  poz=bin(va);
						if(x[poz]!=va)
							printf("-1\n");
						else
							printf("%d\n",poz);
						break;
				     }
			case 1 : {  poz=bin(va);
						printf("%d\n",poz);
						break;
				     }
					 
		    case 2 : {	poz=bin2(va);
			            printf("%d\n",poz);
				        break;
			         }
        }
	}
	
	return 0;
}