#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 low, int high, int val){
    if(low == high)
        return low;
    int mid = low + (high - low) / 2;
    if(v[mid] > val)
        return bin(v, low, mid-1, val);
    else
        return bin(v, mid+1, high, val);
    return -low;
}

int main()
{
    FILE* input = freopen("cautbin.in", "r", stdin);
    FILE* output = 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;
    scanf("%d", &num);

    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;
    }

    fclose(input);
    fclose(output);
    return 0;
}