#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;
    scanf("%d", &n);

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

    int num;
    scanf("%d", &num);

    int ques[num];
    int numbers[num];
    for(i = 0; i < num; i++){
        scanf("%d", &ques[i]);
        scanf("%d", &numbers[i]);
    }


    int index;
    for(i = 0; i < num; i++){
        index = bin(v, 0, n, numbers[i]);
        if(ques[i] == 0)
            printf("%d\n", op0(v, index, n));
        else if(ques[i] == 1)
            printf("%d\n", op1(v, index, n));
        else if(ques[i] == 2)
            printf("%d\n", op2(v, index, n));
    }

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