#include <stdio.h>
#include <assert.h>
#define DIM 100005

int a[DIM], x, n;

int cb1(int k)
{
	int pi,ps,mid;
	for (pi=1, ps=n; pi<=ps;)
		{
			mid=pi+(ps-pi)/2;
			if (k<a[mid]) ps=mid-1;
			else
				if (k>a[mid]) pi=mid+1;
			else return mid;
		}
		return -1;
}

int cb2(int k)
{
	int pi,ps,mid,poz;
	poz=0;
	for (pi=1, ps=n; pi<=ps;)
		{
			mid=pi+(ps-pi)/2;
			if (k>=a[mid]) poz=mid, pi=mid+1;
			else ps=mid-1;
		}
	return poz;
}

int cb3(int k)
{
	int pi,ps,mid,poz=n+1;
	for	(pi=1, ps=n; pi<=ps;)
		{
			mid=pi+(ps-pi)/2;
			if (k<=a[mid]) poz=mid, ps=mid-1;
			else pi=mid+1;
		}
	return poz;
}


int main()
{
	int m,i,op;
	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);
	while (m)
		{
			scanf("%d%d",&op,&x);
			if (op==0)
				printf("%d\n", cb1(x));
			if (op==1)
				printf("%d\n", cb2(x));
			if (op==2)
				printf("%d\n", cb3(x));
            --m;
		}
	return 0;
}