#include <cstdio>
#define DIM 100000

int n, m, v[DIM];

int bin0(int st, int dr, int x)
{
    printf("st %d; dr %d; \n", st, dr);
    if (st > dr)
        return -1;

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

    if (v[mij] == x)
        return bin0(st, mij - 1, x);
/*    {
        for (; v[mij] == x && mij <= n; mij++) ;
        return mij - 1;
    }
*/
    else
        if (v[mij] > x)
            return bin0(st, mij - 1, x);
        else
            return bin0(mij + 1, dr, x);
}

int bin1(int st, int dr, int x)
{
    if (st > dr)
        return dr;

    int mij = st + (dr - st) / 2;
    if (v[mij] == x)
         return bin1(st, mij - 1, x);
/*    {
        for (; v[mij] == x && mij <= n; mij++) ;
        return mij - 1;
    }
*/
    else
        if (v[mij] > x)
            return bin1(st, mij - 1, x);
        else
            return bin1(mij + 1, dr, x);

}

int bin2(int st, int dr, int x)
{
    if (st > dr)
        return st;

    int mij = st + (dr - st) / 2;
    if (v[mij] == x)
        return  bin2(st, mij - 1, x);
 /*   {
        for (; v[mij] == x && mij > 0; mij--);
        return mij + 1;
    }
*/
    else
        if(v[mij] > x)
            return  bin2(st, mij - 1, x);
        else
            return  bin2(mij + 1, dr, x);

}

int main()
{
    FILE *f = fopen("cautbin.in", "r");
    fscanf(f, "%d", &n);
    int i;
    for (i = 1; i <= n; i++)
        fscanf(f, "%d", &v[i]);

    fscanf(f, "%d", &m);

    FILE *g = fopen("cautbin.out", "w");
    int tip, x;
    for (i = 1; i <= m; i++)
    {
        fscanf(f, "%d%d", &tip, &x);
        if (tip == 0)
            fprintf(g, "%d\n", bin0(1, n, x));

        if (tip == 1)
            fprintf(g, "%d\n", bin1(1, n, x));

        if (tip == 2)
            fprintf(g, "%d\n", bin2(1, n, x));


    }

    fclose(g);
    fclose(f);
    return 0;
}