#include<stdio.h>

#define nmax 100001

int v[nmax],n,m;
int rez0(int);
int rez1(int);
int rez2(int);

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&v[i]);
    scanf("%d",&m);
    int a,b;
    for(int i=1;i<=m;++i)
        {
        scanf("%d%d",&a,&b);
        if (a==0)
            printf("%d\n",rez0(b));
        else
        if (a==1)
            printf("%d\n",rez1(b));
        else
            printf("%d\n",rez2(b));
        }
    return 0;
}

int rez0(int x)
{
	int lo, hi, mid;
	for (lo = 1, hi = n; lo <= hi; )
	{
		mid = lo + (hi-lo) / 2;
		if (x < v[mid]) hi = mid-1;
		else if (v[mid] < x) lo = mid+1;
		else return mid;
	}
	return -1;
}

int rez1(int x)
{
	int lo, hi, mid, last = 0;

	for (lo = 1, hi = n; lo <= hi; )
	{
		mid = lo + (hi-lo) / 2;
		if (v[mid] <= x) last = mid, lo = mid+1;
		else hi = mid-1;
	}
	return last;
}

int rez2(int x)
{
	int lo, hi, mid, last = n+1;

	for (lo = 1, hi = n; lo <= hi; )
	{
		mid = lo + (hi-lo) / 2;
		if (x <= v[mid]) last = mid, hi = mid-1;
		else lo = mid+1;
	}
	return last;
}