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

int maxSearch(int, int, int*, int);
int maxLowerSearch(int, int, int*, int);
int maximum(int, int);
int minHigherSearch(int, int, int*, int);

int main() {

    FILE *f, *g;
    f = fopen("cautbin.in", "r");
    g = fopen("cautbin.out", "w");

    int n;
    fscanf(f, "%d", &n);

    int *v = malloc(n * sizeof(int));
    int i;
    for (i = 0; i < n; ++i) {
        fscanf(f, "%d", &v[i]);
    }

    int query_number;

    fscanf(f, "%d", &query_number);

    while (query_number-- ) {
        int current_query, x;
        fscanf(f, "%d %d", &current_query, &x);
        if (current_query == 0) {
            fprintf(g, "%d\n", 1 + maxSearch(0, n - 1, v, x));

        } else if (current_query == 1) {
            fprintf(g, "%d\n", 1 + maxLowerSearch(0, n - 1, v, x));
        } else {
            fprintf(g, "%d\n", 1 + minHigherSearch(0, n - 1, v, x));
        }

    }

    return 0;
}

int maxSearch(int st, int dr, int *v, int x) {
    if (st > dr) { return -2;}
    if (st == dr) {
        if (v[st] != x) return -2;
        else return dr;
    } else {
        int mij = (st + dr) / 2;
        if (v[mij] > x) {
            return maxSearch(st, mij, v, x);
        }
        if (v[mij] < x) {
            return maxSearch(mij + 1, dr, v, x);
        }
        while ( mij <= dr && v[mij] == x) {
            mij ++;
        }
        return mij - 1;
    }
}

int maxLowerSearch(int st, int dr, int *v, int x) {
    if (st > dr) { return -1;}
    if (st == dr) {
        if (v[st] > x) return -1;
        else return dr;
    }
    else {
        int mij = (st + dr) / 2;
        if (v[mij] <= x) {
            return maximum(mij, maxLowerSearch(mij + 1, dr, v, x) );
        } else { return maxLowerSearch(st, mij, v, x); }
    }
}

int maximum(int x, int y) {
    return ( (x < y)? y:x );
}

int minHigherSearch(int st, int dr, int *v, int x) {
    if (st > dr) { return -1;}
    if (st == dr) {
        return dr;
    }
    else {
        int mij = (st + dr) / 2;
        if (v[mij] >= x) {
            return minHigherSearch(st, mij, v, x);
        } else { return minHigherSearch(mij + 1, dr, v, x); }
    }
}