#include <stdio.h>
#include <stdlib.h>

long int cautareBinaraLast(long int *v, long int p, long int q, long int x)
{
    if (p > q)
    {
        return -1;
    }
    long int m = (p + q) / 2;
    if (v[m] == x)
    {
        if (v[m + 1] == x)
        {
            return cautareBinaraLast(v, m + 1, q, x);
        }
        else
        {
            return m;
        }
    }
    if (v[m] > x)
    {
        return cautareBinaraLast(v, p, m - 1, x);
    }
}

long int cautareBinaraFirst(long int *v, long int p, long int q, long int x)
{
    if (p > q)
    {
        return -1;
    }
    long int m = (p + q) / 2;
    if (v[m] == x)
    {
        if (v[m - 1] == x)
        {
            return cautareBinaraFirst(v, p, m - 1, x);
        }
        else
        {
            return m;
        }
    }
    if (v[m] < x)
    {
        return cautareBinaraFirst(v, m + 1, q, x);
    }
}

int main()
{

    FILE *in, *out;
    in = fopen("cautbin.in", "r");
    out = fopen("cautbin.out", "w");

    long int N, M, v[100000], i, x, res;
    int type;

    fscanf(in, "%ld", &N);
    for (i = 1; i <= N; i++)
    {
        fscanf(in, "%ld", &v[i]);
    }

    fscanf(in, "%ld", &M);
    for (i = 1; i <= M; i++)
    {
        fscanf(in, "%d %ld", &type, &x);
        if ((type == 0) || (type == 1))
        {
            res = cautareBinaraLast(v, 1, N, x);
            fprintf(out, "%ld\n", res);
        }
        else
        { // type == 2
            res = cautareBinaraFirst(v, 1, N, x);
            fprintf(out, "%ld\n", res);
        }
    }

    fclose(in);
    fclose(out);

    return 0;
}