#include<stdio.h>
int n,m,x,l,t,i;
int v[100001];
int bs(int x)
	{
		int st,dr,med,last=0;
		st=1;
		dr=n;
		while(st<=dr)
			{
				med=st+(dr-st)/2;
				if(x>=v[med])
					{
						last=med;
						st=med+1;
					}
				else
					dr=med-1;
			}	
		return last;
	}
int bs1(int x)
	{
		int st,dr,med,last=0;
		st=1;
		dr=n;
		while(st<=dr)
			{
				med=st+(dr-st)/2;
				if(x<=v[med])
					{
						dr=med-1;
						last=med;
					}	
				else
					st=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",&v[i]);
	scanf("%d",&m);
	for(i=1;i<=m;i++)
		{
			scanf("%d%d",&t,&x);
			if(t==0)
				{
					l=bs(x);
					if(v[l]!=x)
						printf("-1\n");
					else
						printf("%d\n",l);
				}
			if(t==1)
				{
					l=bs(x);
					printf("%d\n",l);
				}
			if(t==2)
				{
					l=bs1(x);
					printf("%d\n",l);
				}	
		}
	return 0;
}