#include<stdio.h>
#define MAX 100005
int n,i,mod,x,nr;
int a[MAX];

int caut1(int x)
{
	int li=1,ls=n,mij;
	while(li<=ls)
	{
		mij=(li+ls)/2;
		if(a[mij]<x||(a[mij]==x&&a[mij+1]==x))
			li=mij+1;
		else
			ls=mij-1;
	}
	if(a[li]==x)
		return li;
	else
		return -1;
}
int caut2(int x)
{
	int li=1,ls=n,mij,el=0;
	while(li<=ls)
	{
		mij=(li+ls)/2;
		if(a[mij]<=x)
		{
			el=mij;
			li=mij+1;
		}
		else
			ls=mij-1;
	}
	return el;
}
int caut3(int x)
{
	int li=1,ls=n,mij,el=n+1;
	while(li<=ls)
	{
		mij=(li+ls)/2;
		if(a[mij]>=x)
		{
			el=mij;
			ls=mij-1;
		}
		else
			li=mij+1;
	}
	return el;
}
int main(void)
{
	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",&nr);
	for(i=1;i<=nr;i++)
	{
		scanf("%d%d",&mod,&x);
		if(mod==0)
		printf("%d\n",caut1(x));
		if(mod==1)
		printf("%d\n",caut2(x));
		if(mod==2)
		printf("%d\n",caut3(x));
  
	}
	return 0;
}