#include <stdio.h>

#define maxn 100001

int v[maxn], n,m,g;

int caut0(int x)
{
	int st=1, dr=n, m;
    while(st<=dr)
    {
        m=(st+dr)/2;
        v[m]>x ? dr=m-1 : st=m+1;
    }
    m=(st+dr)/2;

    if(v[m]>x)
	{
		m--;
	}

    return m;
}

int caut1(int x)
{
	int st=1, dr=n, m;
    while(st<dr)
    {
        m=(st+dr)/2;
        v[m]>x ? dr=m-1 : st=m+1;
    }
    m=(st+dr)/2;
    if(v[m]>x)
        m--;
    return m;
}

int caut2(int x)
{
	int st=1, dr=n, m;
    while(st<dr)
    {
        m=(st+dr)/2;
        v[m]<x ? st=m+1 : dr=m;
    }
    m=(st+dr)/2;
    if(v[m]<x)
        m--;
    return m;
}

int main()
{
	freopen("cautbin.in", "r", stdin);

	scanf("%d", &n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d", &v[i]);
	}
	scanf("%d", &m);

	freopen("cautbin.out", "w", stdout);

	int t;
	for(int i=0;i<m;i++)
	{
		scanf("%d%d", &t, &g);
		switch(t)
		{
			case 0: printf("%d\n",caut0(g)); break;
			case 1: printf("%d\n",caut1(g)); break;
			case 2: printf("%d\n",caut2(g)); break;
		}
	}


	return 0;
}