#include <stdio.h>

#define MAX_N 5000


int v[MAX_N];


int algBinarySearchL(int n, int x)
{
    int i, step;

    for(step = 1; step < n; step *= 2)

        i = 0;
    while(step != 0)
    {
        if(i + step <= n && v[i + step] <= x)
            i += step;
        step /= 2;
    }

    return i;
}

int algBinarySearchH(int n, int x)
{

    int i, step;

    i = n;
    step = 1;
    while(step < n)
    {
        if(i - step <= n && v[i - step] >= x)
            i -= step;
        step *= 2;
    }

    return i;
}



int main() {
    FILE *fin = fopen("cautbin.in", "r"),
            *fout = fopen("cautbin.out", "w");
    int n;
    int t;

    fscanf(fin, "%d", &n);
    for (int i = 1; i <= n; i++)
        fscanf(fin, "%d", &v[i]);

//    printf("%d\n", algBinarySearchH(n, x));

    for (fscanf(fin, "%d", &t); t; t--) {
        int c, x;
        fscanf(fin, "%d %d", &c, &x);

        int l = algBinarySearchL(n, x);

        if (c == 0)
            fprintf(fout, "%d\n", v[l] == x ? l : -1);
        else if (c == 1)
            fprintf(fout, "%d\n", l);
        else if (c == 2)
            fprintf(fout, "%d\n", algBinarySearchH(n, x));

    }


    fclose(fin);
    fclose(fout);
    return 0;
}