#include <stdio.h>
#define N 100001

int v[N];
int i, m, n, opt, nr;

int CB0(int nr, int st, int dr)
{

    int mij = st + (dr - st)/2;

    if((dr - st) == 1) {
        if (v[mij] == nr) return mij;
        if (mij + 1 == n && v[mij + 1] == nr) return n;
        return -1;
    }

    if(v[mij] <= nr)
        return CB0(nr, mij, dr);
    return CB0(nr, st, mij);
}

int CB1(int nr, int st, int dr)
{

    int mij = st + (dr - st)/2;

    if((dr - st) == 1)
    {
        if(v[dr] > nr)
            return mij;
        else
            return mij + 1;
    }
    if(v[mij] <= nr)
        return CB1(nr, mij, dr);
    return CB1(nr, st, mij);
}

int CB2(int nr, int st, int dr)
{

    int mij = st + (dr - st)/2;

    if((dr - st) == 1)
    {
        if(v[mij] < nr)
            return mij + 1;
        else
            return mij;
    }
    if(v[mij] < nr)
        return CB2(nr, mij, dr);
    return CB2(nr, st, mij);
}

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

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

    scanf("%d", &m);
    for(i = 0; i < m; i++)
    {
        scanf("%d %d", &opt, &nr);
        switch(opt)
        {
            case 0:
                printf("%d\n", CB0(nr, 1, n));
                break;
            case 1:
                printf("%d\n", CB1(nr, 1, n));
                break;
            case 2:
                printf("%d\n", CB2(nr, 1, n));
                break;
        }
    }

    return 0;
}