#include <stdio.h>
#define N 100001

int n, v[N];

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

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

    if(((dr - st) == 1 || dr == st) && v[mij] != nr)
        return -1;

    if(((dr - st) == 1) || dr == st)
        return mij;

    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;
   // printf("%d - %d => %d\n", st, dr, v[mij]);
    if((dr - st) == 1)
    {
        if(v[st] <= n)
            return st;
        else
            return dr;
    }
    if(v[mij] < nr)
        return CB1(nr, mij, dr);
    if(v[mij] > nr)
        return CB1(nr, st, mij);
    return CB1(nr, mij, dr);
}

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);
    if(v[mij] > nr)
        return CB2(nr, st, mij);
    return CB2(nr, st, mij);
}

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

    int i, m, opt, nr;

    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;
}