#include <cstdio>
using namespace std;

int a[100005],b,intr,n,i,m,ok=0,mij,li,ls,poz;
int i1(int x)
{
	int mid;
	ok=0;
	li=-1;
	ls=n;
	while((li<=ls)&&(!ok))
	{
		mid=li+(ls-li)/2;
		if(x==a[mid])
			return mid;
		 if(x<a[mid])
		  ls=mid-1;
		 else
		  li=mid+1;
	}
	return -2;
}
int i2(int x)
{
	int mid;
	ok=0;
	li=-1;
	ls=n;
	while(li<=ls)
	{
		mid=li+(ls-li)/2;
		if(x==a[mid])
			return mid;
		if(x<a[mid])
		  ls=mid-1;
		else
		  {li=mid+1;poz=mid;}
	}
	return poz;
}
int i3(int x)
{
	int mid;
	ok=0;
	li=-1;
	ls=n;
	while(li<=ls)
	{
		mid=li+(ls-li)/2;
		if(x==a[mid+1]) return mid+1;
		if(x==a[mid-1]) return mid-1;
		if(x==a[mid]) return mid;
		if(x<a[mid])
		  {ls=mid-1;poz=mid;}
		else
		  li=mid+1;
	}
	if(a[poz-1]>x)
		return poz-1;
	if(a[poz+1]>x)
		return poz+1;
	return poz;
}
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d %d",&intr,&b);
		switch(intr)
		{
			case 0 :printf("%d\n",i1(b)+1);break;
			case 1 :printf("%d\n",i2(b)>=n?n:i2(b)+1);break;
			case 2 :printf("%d\n",i3(b)+1);break;
		}
	}
	return 0;
}