#include <stdio.h>

#define N 100001 /* Nr maxim de elemente ale sirului, decalat cu 1 */
#define INPUT "cautbin.in" /* Fisierul de intrare */
#define OUTPUT "cautbin.out" /* Fisierul de iesire */


/**
 * 0 x - cea mai mare pozitie pe care se afla un element cu valoarea x sau
 * -1 daca aceasta valoare nu se gaseste in sir
 */
int cautbin0(int [], int, int, int);
/**
 * 1 x - cea mai mare pozitie pe care se afla un element cu valoarea mai
 * mica sau egala cu x
 */
int cautbin1(int [], int, int, int);
/**
 * 2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai
 * mare sau egala cu x
 */
int cautbin2(int [], int, int, int);

int main(void) {

    int a[N], n, m, i, val;
    short tip;

    (void) freopen(INPUT, "r", stdin);
    (void) freopen(OUTPUT, "w", stdout);

    scanf("%d", &n);

    for(i = 1; i <= n; ++i)
        scanf("%d", &a[i]);

    scanf("%d", &m);

    while(m--) {

        scanf("%hd %d", &tip, &val);

        switch(tip) {

            case 0:
                printf("%d\n", cautbin0(a, 1, n, val));
                break;
            case 1:
                printf("%d\n", cautbin1(a, 1, n, val));
                break;
            case 2:
                printf("%d\n", cautbin2(a, 1, n, val));
                break;
        }
    }

    return 0;
}

/**
 * Ia sirul de numere, cea mai mica pozitie, cea mai mare si elementul
 * pentru care trebuie sa gaseasca raspunsul la intrebarea 1, apoi
 * returneaza raspunsul
 */
int cautbin0(int a[], int lo, int hi, int n) {

    int mid;

    /* Cautare binara */
    while(lo <= hi) {

        mid = lo + (hi - lo) / 2; /* Evitam integer overflow-ul */

        if(a[mid] <= n)
            lo = mid + 1;
        else
            hi = mid - 1;
    }

    mid = lo + (hi - lo) / 2;

    if(a[mid] > n)
        --mid;

    if(a[mid] == n)
        return mid;
    return -1;
}

/**
 * Ia sirul de numere, cea mai mica pozitie, cea mai mare si elementul
 * pentru care trebuie sa gaseasca raspunsul la intrebarea 2, apoi
 * returneaza raspunsul
 */
int cautbin1(int a[], int lo, int hi, int n) {

    int mid;

    while(lo < hi) {

        mid = lo + (hi - lo) / 2;

        if(a[mid] <= n)
            lo = mid + 1;
        else
            hi = mid;
    }

    mid = lo + (hi - lo) / 2;

    if(a[mid] > n)
        --mid;

    return mid;
}

/**
 * Ia sirul de numere, cea mai mica pozitie, cea mai mare si elementul
 * pentru care trebuie sa gaseasca raspunsul la intrebarea 3, apoi
 * returneaza raspunsul
 */
int cautbin2(int a[], int lo, int hi, int n) {

    int mid;

    while(lo < hi) {

        mid = lo + (hi - lo) / 2;

        if(a[mid] < n)
            lo = mid + 1;
        else
            hi = mid;
    }

    mid = lo + (hi - lo) / 2;

    if(a[mid] < n)
        ++mid;

    return mid;
}