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