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

#define IN "cautbin.in"
#define OUT "cautbin.out"
#define NMAX 100000

void read (int *n, int *v, int *t){
    int k, i;

    scanf ("%d", &k), *n = k;

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

    scanf ("%d", &k), *t = k;
}

int binSearch0 (int n, int *v, int x){
    int right, left, midle, pos;

    left = 0, right = n - 1;
    pos = -2;

    while (left <= right){
        midle = (left + right) / 2;

        if (v [midle] == x)
            pos = midle;

        if (v [midle] <= x)
            left = midle + 1;
        else
            right = midle - 1;
    }

    return pos + 1;
}

int binSearch1 (int n, int *v, int x){
    int right, left, midle, pos;

    left = 0, right = n - 1;

    while (left <= right){
        midle = (left + right) / 2;

        if (v [midle] <= x) {
            left = midle + 1;
            pos = midle;
        }
        else
            right = midle - 1;
    }

    return pos + 1;
}

int binSearch2 (int n, int *v, int x){
    int right, left, midle, pos;

    left = 0, right = n - 1;

    while (left <= right){
        midle = (left + right) / 2;

        if (v [midle] < x)
            left = midle + 1;
        else{
            pos = midle;
            right = midle - 1;
        }
    }

    return pos + 1;
}

int main(void){
    freopen (IN, "r", stdin);
    freopen (OUT, "w", stdout);

    int n, v[NMAX], t, k, x;

    read(&n, v, &t);

    while (t--){
        scanf ("%d%d", &k, &x);

        switch(k){
            case 0:
                printf ("%d\n", binSearch0 (n, v, x));
                break;
            case 1:
                printf ("%d\n", binSearch1 (n, v, x));
                break;
            case 2:
                printf ("%d\n", binSearch2 (n, v, x));
                break;
        }
    }

    fclose (stdin);
    fclose (stdout);
    return 0;
}