#include <stdio.h>
#include <stdlib.h>
#define N 100010
int v[N];



int bs0(int st, int dr, int x) {
    int m;
    if(st>dr) return -1;
    else {
        m = st + (dr - st) / 2;
        if(v[m] < x) return bs0(m+1,dr,x);
        else  if(v[m] > x) return bs0(st, m-1,x);
            else
                {
                    if(m == dr) return m;
                    else
                        if(v[m+1] > x) return m;
                        else return bs0(m+1,dr,x);
                }
    }
}

int bs1(int st, int dr, int x){
    int m;
    m = st + (dr - st) / 2;
    if(v[m] > x) return bs1(st, m -1, x);
    else {
        if(m == dr) return m;
        else
            if(v[m+1] > x) return m;
            else return bs1(m+1,dr,x);
    }
}

int bs2(int st, int dr, int x){
    int m;
    m = st + (dr - st) / 2;
    if(v[m] < x) return bs2(m+1, dr, x);
    else {
        if(m == st) return m;
        else
            if(v[m-1] < x) return m;
            else return bs2(st, m-1,x);
    }
}

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", bs0(1, n, val));
          if (tip == 1)
             printf("%d\n", bs1(1, n, val));
          if (tip == 2)
             printf("%d\n", bs2(1, n, val));
    }
    exit(0);
}