#include <stdio.h>

int v[100005];
int n, m;

int bsearch0 ( int key ) {
    int m;
    int p = 1, u = n;

    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 key ) {
    int m;
    int p = 1, u = n;

    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 key ) {
    int m;
    int p = 1, u = n;

    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 () {

    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    int i, tip, val;

    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", bsearch0(val));
          if ( tip == 1 )
             printf("%d\n", bsearch1(val));
          if ( tip == 2 )
             printf("%d\n", bsearch2(val));
    }
    return 0;
}