#include <stdio.h>
#include <stdlib.h>
int v[100011];
int X0(int dr, int val) {
    int med, st = 1;
    while (st <= dr) {
        med = (st + dr) >> 2;
        if (v[med] <= val)
            st = med + 1;
        else
            dr = med - 1;
    }
    if (v[st] > val)
        st --;
    if (v[st] == val)
        return st;
    return -1;
}
int X1 (int dr, int val) {
    int med, st = 1;
    while (st < dr){
        med = (st + dr) >> 2;
        if (v[med] <= val)
            st = med + 1;
        else
            dr = med;
    }
    if (v[st] > val)
       st --;
    return st;
}
int X2 (int dr, int val) {
    int med, st = 1;
    while (st < dr) {
        med = (st + dr) >> 2;
        if (v[med] < val)
             st = med + 1;
        else
            dr = med;
    }
   if (v[st] < val)
       st ++;
    return st;
}
int main () {
    FILE *fin, *fout;
    fin = fopen("cautbin.in", "r");
    fout = fopen("cautbin.out", "w");
    int i, n, m, op, val;
    fscanf(fin, "%d", &n);
    for (i = 1; i <= n; ++ i)
        fscanf(fin, "%d", &v[i]);
    fscanf(fin, "%d", &m);
    for (i = 1; i <= m; i ++){
          fscanf(fin, "%d%d", &op, &val);
          if (op == 0)
             fprintf(fout, "%d\n", X0(n, val));
          else
             if (op == 1)
                fprintf(fout, "%d\n", X1(n, val));
             else
                if (op == 2)
                    fprintf(fout, "%d\n", X2(n, val));
    }
    fclose(fin);
    fclose(fout);
    return 0;
}