#include <stdio.h>
#include <stdlib.h>

int n, *a;

int caut (int i, int j, int x, int y)   {
    if (i == j)  {
          if (a [i] ==  y ) return i;
          else 
               if (x == 0) return -1;
          else
               if (x == 2) return i+1;
          else return i-1;
          }
    else 
     if (x == 1) {
           int m = (i+j)/2;
     if (a [m] >= y) return caut (i, m, x, y);
        else return caut (m+1, j, x, y);     
           }
     else {
     int m = (j+i+1)/2;
     if (a [m] > y) return caut (i, m-1, x, y);
        else return caut (m, j, x, y); 
        }
}

int main () {
   
   FILE *fin = fopen ("cautbin.in", "r");
   FILE *fout = fopen ("cautbin.out", "w");
   fscanf (fin, "%d", &n);
   
   int i, m, x, y;
   a = malloc ((n+2) * sizeof (int));
   for (i=1; i<=n; ++i) 
       fscanf (fin, "%d", &a [i]);
   
   fscanf (fin, "%d", &m);
   
   for (i=0; i<m; ++i) {
       fscanf (fin, "%d %d", &x, &y);
       fprintf (fout, "%d\n", caut (0, n, x, y));
       //printf ("%d\n", caut (1, n, x, y));
}
 
 fclose (fin);
 fclose (fout);
 return 0;   
}