#include <cstdio>

using namespace std;

int n,m,v[100001];

int Intrebare0(int x)
{
    int l,m,h,pos=-1;
    l = 0;
    h = n-1;
    while(l <= h)
    {
        m = l + (h-l)/2;
        if(x == v[m])
           pos = m;
        if(x >= v[m])
            l = m+1;
        else if(x <= v[m])
            h = m-1;
    }
    return pos;
}

int Intrebare1(int x)
{
    int l,m,h;
    l = 0;
    h = n-1;
    while(l <= h)
    {
        m = l + (h-l)/2;
        //printf("%d %d %d\n",l,m,h);
        if(x >= v[m])
            l = m+1;
        else if(x <= v[m])
            h = m-1;
    }
    if(x < v[m])
        return m-1;
    else
        return m;
}

int Intrebare2(int x)
{
    int l,m,h;
    l = 0;
    h = n-1;
    while(l < h)
    {
        m = l + (h-l)/2;
        if(x > v[m])
            l = m+1;
        else
            h = m;
    }
    m = l + (h-l)/2;
    if(x > v[m])
        ++m;
    return m;
}

void Read()
{
    int tp, x;
    FILE *f = fopen("cautbin.in","r");
    FILE *g = fopen("cautbin.out","w");
    fscanf(f,"%d",&n);
    for(int i=0;i<n;i++)
        fscanf(f,"%d",&v[i]);
    fscanf(f,"%d",&m);
    for(int i=0;i<m;i++)
    {
        fscanf(f,"%d %d",&tp,&x);
        if(tp == 0)
            fprintf(g,"%d\n",Intrebare0(x)+1);
        if(tp == 1)
            fprintf(g,"%d\n",Intrebare1(x)+1);
        if(tp == 2)
            fprintf(g,"%d\n",Intrebare2(x));
    }
}

int main()
{
    Read();
    return 0;
}