#include <fstream>
#define N 100010
using namespace std;

ifstream f ("cautbin.in");
ofstream g ("cautbin.out");

int v[N], val;

int bsearch0 (int p, int u, int key) {
    int m;

    while (p <= u) {
        m = (p + u) / 2;
        if (v[m] <= key)
            p = m + 1;
        else
            u = m - 1;
    }
    m = (p + u) / 2;

    if (v[m] > key) m --;
    if (v[m] == key)
        return m;
    return -1;
}
int bsearch1 (int p, int u, int key) {
    int m, n = u;

    while (p < u){
        m = (p + u) / 2;
        if (v[m] <= key)
            p = m + 1;
        else
            u = m;
    }

    m = (p + u) / 2;
    if (v[m] > key)
       -- m;
    return m;
}
int bsearch2 (int p, int u, int key) {
    int m;

    while (p < u) {
        m = (p + u) / 2;
        if (v[m] < key)
            p = m + 1;
        else
            u = m;
    }

    m = (p + u) / 2;
    if (v[m] < key)
       ++ m;
    return m;
}

int main(){

    int n, i, x, q, ind, val;

    f >> n;

    for( i = 1; i <= n; ++i )
        f >> v[ i ];

    f >> q;

    for( i = 1; i <= q; ++i ){
        f >> ind >> val;
        if( ind == 0 )
            g << bsearch0( 1, n, val ) << "\n";
        if( ind == 1 )
            g << bsearch1( 1, n, val ) << "\n";
        if( ind == 2 )
            g << bsearch2( 1, n, val ) << "\n";
    }

    return 0;
}