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

int bs0(int p, int u, int flag) {
    int m;
    while (p<= u) {
        m = (p + u) / 2;
        if (v[m]<=flag)
            p =m+1;
        else
            u =m-1;
    }
    m = (p+u) / 2;
    if (v[m] >flag) m --;
    if (v[m]==flag)
        return m;
    return -1;
}
int bs1 (int p, int u, int flag) {
    int m,n=u;
    while (p<u){
        m = (p+u) / 2;
        if (v[m]<=flag)
            p=m+1;
        else
            u=m;
    }
    m =(p+u)/2;
    if (v[m]>flag)
       m--;
    return m;
}
int bs2 (int p, int u, int flag) {
    int m;
    while (p<u) {
        m=(p + u)/2;
        if (v[m]<flag)
             p=m+1;
        else
            u=m;
    }
    m =(p+u)/2;
   if (v[m]<flag)
       m++;
    return m;
}
int main () {
    int i,n,m,fel,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", &fel, &val);
          if (fel==0)
             printf("%d\n",bs0(1,n,val));
          if (fel==1)
             printf("%d\n",bs1(1,n,val));
          if (fel==2)
             printf("%d\n",bs2(1,n,val));
    }
    return 0;
}