#include <stdio.h>

#include <stdlib.h>

#define N 100010

int v[N];



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 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", bsearch0(1, n, val));

          if (tip == 1)

             printf("%d\n", bsearch1(1, n, val));

          if (tip == 2)

             printf("%d\n", bsearch2(1, n, val));

    }

    exit(0);

}