#include<stdio.h>
#define nmax 100005

int a[nmax];
int n,mm;

int search0(int s,int f, int val)
{
	int m;
	while(s<=f)
	{
		m=(s+f)/2;
		if(a[m]<=val)
			s=m+1;
		else
			f=m-1;
	}
	if(a[m]>val)
		m--;
	if(a[m]==val)
		return m;
	return -1;
}

int search1(int s,int f, int val)
{
	int m;
	while(s<f)
	{
		m=(s+f)/2;
		if(a[m]<=val)
			s=m+1;
		else
			f=m;
	}
	m=(s+f)/2;
	if(a[m]>val)
		m--;
	return m;
}

int search2(int s,int f, int val)
{
	int m;
	while(s<f)
	{
		m=(s+f)/2;
		if(a[m]<val)
			s=m+1;
		else
			f=m;
	}
	m=(s+f)/2;
	if(a[m]<val)
		m++;
	return m;
}

int main()
{
	int i,x,y;
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d ",&a[i]);
	
	scanf("%d",&mm);
	for(i=1;i<=mm;i++)
	{
		scanf("%d %d",&x,&y);
		if(x==0)
			printf("%d\n",search0(1,n,y));
		if(x==1)
			printf("%d\n",search1(1,n,y));
		if(x==2)
			printf("%d\n",search2(1,n,y));
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}