#include <stdio.h>
#define M 100050

int cautare_binara (int v[], int n, int x, int pas, int tip)
{
    int i;
    for(i = 0; pas; pas >>= 1) {
        if (i + pas <= n && v[i+pas] <= x) {
            i += pas;
        }
    }

    if (tip == 1 || (tip == 0 && v[i] == x)) {
        return i;
    }
    if (tip == 0 && v[i] != x) {
        return -1;
    }

    if (v[i] != x) {
        return i+1;
    }

    while (v[i] == v[i-1]) {
        i --;
    }

    return i;
}

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

    int n, v[M], m, tip, x, pas;

    scanf ("%d", &n);
    for (pas = 1; pas < n; pas <<= 1);

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

    scanf ("%d", &m);

    for (int i=0; i<m; i++) {
        scanf ("%d %d", &tip, &x);
        printf ("%d\n", cautare_binara(v, n, x, pas, tip));
    }

    return 0;
}