#include <stdio.h>
#include <stdlib.h>
#define N 100010

int v[N]; // Vector de căutare

// Căutare binară - găsește ultima apariție a unei valori
int cautare0(int st, int dr, int cheie) {
    int mij;
    while (st <= dr) {
        mij = (st + dr) / 2;
        if (v[mij] <= cheie)
            st = mij + 1;
        else
            dr = mij - 1;
    }
    mij = (st + dr) / 2;
    if (v[mij] > cheie) mij--;
    if (v[mij] == cheie)
        return mij;
    return -1;
}

// Căutare binară - găsește cea mai mare poziție unde elementul poate fi inserat
int cautare1(int st, int dr, int cheie) {
    int mij;
    while (st < dr) {
        mij = (st + dr) / 2;
        if (v[mij] <= cheie)
            st = mij + 1;
        else
            dr = mij;
    }
    mij = (st + dr) / 2;
    if (v[mij] > cheie)
        --mij;
    return mij;
}

// Căutare binară - găsește prima poziție unde elementul poate fi inserat
int cautare2(int st, int dr, int cheie) {
    int mij;
    while (st < dr) {
        mij = (st + dr) / 2;
        if (v[mij] < cheie)
            st = mij + 1;
        else
            dr = mij;
    }
    mij = (st + dr) / 2;
    if (v[mij] < cheie)
        ++mij;
    return mij;
}

int main() {
    int i, n, m, tip, val;
    
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    
    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
        scanf("%d", &v[i]);
    
    scanf("%d", &m);
    while (m--) {
        scanf("%d%d", &tip, &val);
        if (tip == 0)
            printf("%d\n", cautare0(1, n, val));
        if (tip == 1)
            printf("%d\n", cautare1(1, n, val));
        if (tip == 2)
            printf("%d\n", cautare2(1, n, val));
    }
    exit(0);
}