#include <stdio.h>
#define MAX 100000

int b_search0(unsigned long int v[], int l, int r, int x, int n)
{
    if (l > r)
        return -1;
    int mid = (l + r) / 2;
    if (v[mid] == x && (mid == n - 1 || v[mid + 1] != x))
        return mid;
    return x >= v[mid] ? b_search0(v, mid + 1, r, x, n) : b_search0(v, l, mid - 1, x, n);
}

int b_search1(unsigned long int v[], int l, int r, int x, int n)
{
    if (l > r)
        return -1;
    int mid = (l + r) / 2;
    if (v[mid] <= x && (mid == n - 1 || v[mid + 1] > x))
        return mid;
    return x >= v[mid] ? b_search1(v, mid + 1, r, x, n) : b_search1(v, l, mid - 1, x, n);
}

int b_search2(unsigned long int v[], int l, int r, int x)
{
    if (l > r)
        return -1;
    int mid = (l + r) / 2;
    if (v[mid] >= x && (mid == 0 || v[mid - 1] < x))
        return mid;
    return x <= v[mid] ? b_search2(v, l, mid - 1, x) : b_search2(v, mid + 1, r, x);
}

int main()
{
    FILE *in = fopen("cautbin.in", "r");
    FILE *out = fopen("cautbin.out", "w");
    int n, m, op, x, poz;
    unsigned long int v[MAX];
    fscanf(in, "%d", &n);
    for (int i = 0; i < n; i++)
        fscanf(in, "%lu", v + i);
    fscanf(in, "%d", &m);
    for (int i = 0; i < m; i++)
    {
        fscanf(in, "%d%d", &op, &x);
        switch (op)
        {
        case 0:
            poz = b_search0(v, 0, n - 1, x, n);
            if (poz == -1)
                fprintf(out, "-1\n");
            else
                fprintf(out, "%d\n", poz + 1);
            break;
        case 1:
            fprintf(out, "%d\n", b_search1(v, 0, n - 1, x, n) + 1);
            break;
        case 2:
            fprintf(out, "%d\n", b_search2(v, 0, n - 1, x) + 1);
            break;
        }
    }
    fclose(in);
    fclose(out);
    return 0;
}