#include <stdio.h>
#define MAX 100003
using namespace std;

int n, a[MAX];


void read()
{
    int i;

    scanf("%d", &n);

    for(i = 1; i <= n; i++)
        scanf("%d", &a[i]);
}



int  fquery(int lo, int hi, int x)
{
    int mid, m;

    if(lo > hi)
        return -1;

    mid = lo + (hi - lo) / 2;

    if(x == a[mid])
    {
        m = mid + 1;

        while(x == a[m])
            m++;

        return m - 1;
    }
    else
        {
            if(x > a[mid])
                return fquery(mid + 1, hi, x);
            else
                return fquery(lo, mid - 1, x);
        }
}



int squery(int lo, int hi, int x)
{
    int mid, m;

    if(lo > hi)
        return 0;

    mid = lo + (hi - lo) / 2;

     if(a[mid] <= x)
    {
        m = mid + 1;

        while(a[m] <= x)
            m++;

        return m - 1;
    }
    else
        return squery(lo, mid - 1, x);

}



int tquery(int lo, int hi, int x)
{
    int mid, m;

    if(lo > hi)
        return 0;

    mid = lo + (hi - lo) / 2;

    if(a[mid] >= x)
    {
        m = mid - 1;

        while(a[m] >= x)
            m--;

        return m + 1;
    }
    else
        return tquery(mid + 1, hi, x);
}



void solve()
{
    int i, sw, x, r, m;

    scanf("%d", &m);

    for(i = 1; i <= m; i++)
    {
        scanf("%d", &sw);

        if(sw == 0)
        {
            scanf("%d", &x);
            r = fquery(1, n, x);
            printf("%d\n", r);
        }

        if(sw == 1)
        {
            scanf("%d", &x);
            r = squery(1, n, x);
            printf("%d\n", r);
        }

        if(sw == 2)
        {
            scanf("%d", &x);
            r = tquery(1, n, x);
            printf("%d\n", r);
        }

    }

}



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

    read();

    solve();

    fclose(stdin);
    fclose(stdout);

    return 0;
}