#include<stdio.h>

int a[100002],i,n,m,x,caz,ans;

int bs1(int,int);
int bs2(int,int);
int bs3(int,int);

int main()
{
	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",&m);
	
	for(;m;m--)
	{
		scanf("%d %d",&caz,&x);
		
		if(caz==0)
			ans=bs1(1,n);
		if(caz==1)
			ans=bs2(1,n);
		if(caz==2)
			ans=bs3(1,n);
		
		printf("%d\n",ans);
	}
	
	return 0;
}

int bs1(int l,int r)
{
	int av;
	
	if(l>r)
		return -1;
	else
	{
		av=(l+r)/2;
		if(a[av]==x)
		{
			if(a[av+1]!=x)
				return av;
			else
				return bs1(av+1,r);
		}
		else
		{
			if(a[av]>x)
				return bs1(l,av-1);
			else
				return bs1(av+1,r);
		}
	}
}

int bs2(int l, int r)
{
	int av;
	
	if(l>r)
		return n;
	else
	{
		av=(l+r)/2;
		if(a[av]==x||a[av]<x)
		{
			if(a[av+1]>x)
				return av;
			else
				return bs2(av+1,r);
		}
		else
			return bs2(l,av-1);
	}
}

int bs3(int l, int r)
{
	int av;
	
	if(l>r)
		return 1;
	else
	{
		av=(l+r)/2;
		if(a[av]==x||a[av]>x)
		{
			if(a[av-1]<x)
				return av;
			else
				return bs3(l,av-1);
		}
		else
			return bs3(av+1,r);
	}
}