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

int op0(int* v, int index, int n){
    if(index < 0)
        return -1;
    int i;
    int poz = index;
    for(i = index+1; i < n; i++){
        if(v[i] == v[poz])
            poz = i;
    }
    return poz+1;
}

int op1(int* v, int index, int n){
    if(index < 0)
        return -index + 1;
    return index + 1;
}

int op2(int* v, int index, int n){
    if(index < 0)
        return -index;

    int i;
    int poz = index;
    for(i = index-1; i >= 0; i--){
        if(v[i] == v[poz])
            poz = i;
    }
    return poz+1;
}

int bin(int* v, int p, int u, int key){
    int m;

    while (p <= u) {
        m = (p + u) / 2;
        if (v[m] <= key)
            p = m + 1;
        else
            u = m - 1;
    }
    m = (p + u) / 2;

    if (v[m] > key) m --;
    if (v[m] == key)
        return m;
    return -1;

}

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

    int n, i;
    if(scanf("%d", &n) < 0)
        exit(0);

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

    int num;
    if(scanf("%d", &num) < 0)
        exit(0);

    int ques;
    int number;

    int index;
    int mda = 0;
    for(i = 0; i < num; i++){
        if(scanf("%d", &ques) < 0)
            exit(0);

        if(scanf("%d", &number) < 0)
            exit(0);

        if(i != 0 && mda == number) {}
        else    index = bin(v, 0, n, number);

        if(ques == 0)
            printf("%d\n", op0(v, index, n));
        else if(ques == 1)
            printf("%d\n", op1(v, index, n));
        else if(ques == 2)
            printf("%d\n", op2(v, index, n));

        mda = number;
    }

    return 0;
}