/**
 * user: caen1
 * file: infoarena/cautbin.c
 * date: 23 apr 2011
**/
#include <stdio.h>
 
#define IN "cautbin.in"
#define OUT "cautbin.out"
#define N 100001
#define NF -1
 
static unsigned long v[N], n;
 
static long cautbin_0(long);
static long cautbin_1(long);
static long cautbin_2(long);
 
int main(void) {
 
    long i, m, x;
    int q;
 
    (void) freopen(IN, "r", stdin);
    (void) freopen(OUT, "w", stdout);
 
    (void) scanf("%ld", &n);
    for(i = 1; i <= n; ++i) (void) scanf("%ld", &v[i]);
 
    (void) scanf("%ld", &m);
 
    while(m--) {
 
        (void) scanf("%d %ld", &q, &x);
 
        switch(q) {
 
            case 0:
            printf("%ld\n", cautbin_0(x));
            break;
 
            case 1:
            printf("%ld\n", cautbin_1(x));
            break;
 
            case 2:
            printf("%ld\n", cautbin_2(x));
            break;
        }
    }
 
    return 0;
}
 
long cautbin_0(long x) {
 
    long st = 0, dr = n, mid;
 
    do {
 
        mid = st + (dr - st) / 2;
 
        if(x < v[mid]) dr = mid - 1;
        else st = mid + 1;
    } while(v[mid] != x && st <= dr);
 
    if(v[mid] != x) return NF;
    else while(v[mid + 1] == x) ++mid;
 
    return mid;
}
 
long cautbin_1(long x) {
 
    long st = 0, dr = n, mid;
 
    do {
 
        mid = st + (dr - st) / 2;
 
        if(x < v[mid]) dr = mid - 1;
        else st = mid + 1;
    } while(v[mid] != x && st <= dr);
 
    if(v[mid] > x) --mid;
    if(v[mid] == x) while(v[mid + 1] == x && mid < n) ++mid;
 
    return mid;
}
 
long cautbin_2(long x) {
 
    long st = 0, dr = n, mid;
 
    do {
 
        mid = st + (dr - st) / 2;
 
        if(x < v[mid]) dr = mid - 1;
        else st = mid + 1;
    } while(v[mid] != x && st <= dr);
 
    if(v[mid] < x) ++mid;
    if(v[mid] == x) while(v[mid - 1] == x && mid > 0) --mid;
 
    return mid;
}