#include <cstdio>
using namespace std;

int a[100005],b,intr,n,i,m,ok=0,mij,li,ls;
int cautbin(int x)
{
	int mid;
	ok=0;
	li=-1;
	ls=n;
	while((li!=ls)&&(!ok))
	{
		mid=(li+ls)/2;
		if(x==a[mid])
			ok=1;
		else
		 if(x<a[mid])
		  {ls=mid+1;li+=1;}
		 else
		  {li=mid-1;ls+=1;}
	}
	return mid;
}
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);
		mij=cautbin(b);
		switch(intr)
		{
			case 0 : if(ok) {while(a[mij+1]==a[mij]) mij++; printf("%d\n",mij+1);} else printf("-1\n");break;
		case 1 : printf("%d\n",b<a[mij]?li-1:li);break;
		case 2 : printf("%d\n",b<a[mij]?ls:ls-1);break;
		}
	}
	return 0;
}