#include <stdio.h>
#include <stdlib.h>
#define N 100010
int v[N];
 
int bsearch0 (int a, int b, int key) {
    int m;
 
    while (a <= b) {
        m = (a + b) / 2;
        if (v[m] <= key)
            a = m + 1;
        else
            b = m - 1;
    }
    m = (a + b) / 2;
 
    if (v[m] > key) m --;
    if (v[m] == key)
        return m;
    return -1;
}
 
int bsearch1 (int a, int b, int key) {
    int m, n = b;
 
    while (a < b){
        m = (a + b) / 2;
        if (v[m] <= key)
            a = m + 1;
        else
            b = m;
    }
 
    m = (a + b) / 2;
    if (v[m] > key)
       -- m;
    return m;
}
 
int bsearch2 (int a, int b, int key) {
    int m;
 
    while (a < b) {
        m = (a + b) / 2;
        if (v[m] < key)
            a = m + 1;
        else
            b = m;
    }
    
    m = (a + b) / 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);
}