#include <stdio.h>
#include <stdlib.h>
#define N 100010
int v[N];
 
int cautare_binara (int p, int u, int c) {  // CAUTA CEA MAI MARE POZITIE PE CARE SE AFLA ELEM. C SI RETURNEAZA -1 DACA NU EXISTA IN SIR.
    int m;
    while(p<=u) {
          m=(p+u)/2;
          if(v[m]<=c)
               p=m+1;   //daca v[m]<=c, al "m+1" -lea element devine primul si cautam in a doua parte
          else
               u = m - 1;       // altfel, al "m-1"-lea element devine ultimul si cautam in prima parte.
          }
    m = (p + u) / 2;
    if (v[m] > c) 
             m --;
    if (v[m] == c)
             return m;    //returneaza pozitia pe care l-am gasit pe c
    return -1;
}
 
int cautare_binara1 (int p, int u, int c) { // CAUTA CEA MAI MARE POZITIE PE CARE SE AFLA UN ELEM. <= DECAT C.
    int m, n = u;
    while (p < u){
          m = (p + u) / 2;
          if (v[m] <= c)
                   p = m + 1;
          else
                   u = m;
          }

     m = (p + u) / 2;
     if (v[m] > c)
        -- m;
     return m;
}

int cautare_binara2 (int p, int u, int c) { // CAUTA CEA MAI MICA POZITIE PE CARE SE AFLA UN ELEM. >= DECAT C.
    int m;
    while (p < u) {
          m = (p + u) / 2;
          if (v[m] < c)
              p = m + 1;
          else
              u = m;
          }
 
    m = (p + u) / 2;
    if (v[m] < c)
       ++ m;
    return m;
}
 
int main () {
int i, n, m, tip, val;
FILE *p, *q;
p = fopen("cautbin.in","r");
q = fopen("cautbin.out","w");
fscanf(p, "%d", &n);
for (i = 1; i <= n; ++ i)
    fscanf(p, "%d", &v[i]);

fscanf(p, "%d", &m);
 
while (m --){
      fscanf(p, "%d%d", &tip, &val);
      if (tip == 0)
         fprintf(q, "%d\n", cautare_binara(1, n, val));
      if (tip == 1)
         fprintf(q, "%d\n", cautare_binara1(1, n, val));
      if (tip == 2)
         fprintf(q, "%d\n", cautare_binara2(1, n, val));
         }
fclose(p);
fclose(q);
return 0;
}