#include<stdio.h>
#define Nmax 100002

using namespace std;

FILE *c,*d;
int n,m,a[Nmax];

void read()
{
	int i;
	fscanf(c,"%d",&n);
	for(i=1;i<=n;i++)
		fscanf(c,"%d",&a[i]);
}

int binary_search0(int x)
{
	int l=1,r=n,mid,find=-1;
	while(l<=r)
	{
		mid=l+((r-l)>>1);               // mid=(l+r)/2
		if(a[mid]==x)
		{
			find=mid;
			l=mid+1;
		}
		else
			if(a[mid]<x)
				l=mid+1;
			else					    	// a[mid]>x
				r=mid-1;
	}
	return find;
}

int binary_search1(int x)
{
	int l=1,r=n,mid,find;
	while(l<=r)
	{
		mid=l+((r-l)>>1);
		if(a[mid]<=x)
		{
			find=mid;
			l=mid+1;
		}
		else
			r=mid-1;
	}
	return find;
}

int binary_search2(int x)
{
	int l=1,r=n,mid,find;
	while(l<=r)
	{
		mid=l+((r-l)>>1);
		if(a[mid]>=x)
		{
			find=mid;
			r=mid-1;
		}
		else
			l=mid+1;
	}
	return find;
}

int main()
{
	int i,b,value;
	c=fopen("cautbin.in","r");
	d=fopen("cautbin.out","w");
	read();
	fscanf(c,"%d",&m);
	for(i=1;i<=m;i++)
	{
		fscanf(c,"%d %d",&b,&value);
		if(b==0)
			fprintf(d,"%d\n",binary_search0(value));
		else
			if(b==1)
				fprintf(d,"%d\n",binary_search1(value));
			else
				if(b==2)
					fprintf(d,"%d\n",binary_search2(value));
	}
	fclose(c);
	fclose(d);
	return 0;
}