#include<stdio.h>

#define MAX 100000
int v[MAX];

int poz=-3;
int bsearch0(int* v,int l,int r,int x)
{
	if(l>r)
		return -1;
	int m=(l+r)/2;
	if(v[m]==x)
	{
		poz=m;
		return bsearch0(v,m+1,r,x);
	}
	else
		return bsearch0(v,l,m-1,x);
}

int bsearch1(int* v,int l,int r,int x)
{
	if(l==r)
		return r;
	int m=(l+r)/2;
	if(v[m]<=x)
		return bsearch1(v,m+1,r,x);
	else return bsearch1(v,l,m-1,x);
}

int bsearch2(int* v,int l,int r,int x)
{
	if(l==r)
		return l;
	int m=(l+r)/2;
	if(v[m]>=x)
		return bsearch2(v,l,m-1,x);
	else return bsearch2(v,m+1,r,x);
}

int main()
{
	FILE* f1,*f2;
	int n,m,a,b,i;
	f1=fopen("cautbin.in","r");
	f2=fopen("cautbin.out","w");
	fscanf(f1,"%d",&n);
	for(i=0;i<n;i++)
		fscanf(f1,"%d",&v[i]);
	fscanf(f1,"%d",&m);
	for(i=0;i<m;i++)
	{
		fscanf(f1,"%d %d",&a,&b);
		if(a==0)
		{
			if(bsearch0(v,0,n,b)==-1 && poz!=-3)
				fprintf(f2,"%d\n",poz+1);
			else fprintf(f2,"-1\n");
		}
		else if(a==1)
			fprintf(f2,"%d\n",bsearch1(v,0,n,b)+1);
		else fprintf(f2,"%d\n",bsearch2(v,0,n,b)+1);
	}
	fcloseall();
	return 0;
}