/*
Algoritm de cautare binara.
*/

#include <stdio.h>

#define MAX     100000

int numere[MAX];

int cautbin_0 (int start, int stop, int x) {
    int mid;
    while (start <= stop) {
        mid = start + (stop - start) / 2;
        if (numere[mid] > x)
            stop = mid - 1;
        else {
            if (numere[mid] < x)
                start = mid + 1;
            else
                return mid;
        }
    }
    return -1;
}

int cautbin_1 (int start, int stop, int x) {
    int mid;
    int pos = 1;
    while (start <= stop) {
        mid = start + (stop - start) / 2;
        if (numere[mid] <= x) {
            pos = mid;
            start = mid + 1;
        }
        else
            stop = mid - 1;
    }
    return pos;
}

int cautbin_2 (int start, int stop, int x) {
    int mid;
    int pos = 1;
    while (start <= stop) {
        mid = start + (stop - start) / 2;
        if (numere[mid] >= x) {
            pos = mid;
            stop = mid - 1;
        }
        else
            start = mid + 1;
    }
    return pos;
}

int main () {
    int n, m;
    int q, x;
    int i;

    FILE *f_in = fopen("cautbin.in", "r");
    FILE *f_out = fopen("cautbin.out", "w");

    fscanf(f_in, "%d", &n);
    for (i = 1; i <= n; i++)
        fscanf(f_in, "%d", &numere[i]);
    
    fscanf(f_in, "%d", &m);
    for (i = 0; i < m; i++) {
        fscanf(f_in, "%d %d", &q, &x);
        switch (q) {
            case 0: 
                fprintf(f_out, "%d\n", cautbin_0(1, n, x)); break;
            case 1:
                fprintf(f_out, "%d\n", cautbin_1(1, n, x)); break;
            default:
                fprintf(f_out, "%d\n", cautbin_2(1, n, x)); break;
        }
    }

    fclose(f_in);
    fclose(f_out);
    return 0;
}