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

int cautBinara(int *v, int x, int inc, int sf)
{
  if(inc+1 == sf){ 
                   if(v[sf] <= x) return sf+1;
                   else if(v[inc]<= x) return inc +1;
                   else return inc;
                 }

   int n =(sf + inc)/2;
   if(x < v[n]) return cautBinara(v,x,inc,n);
   else if(x >= v[n]) return cautBinara(v,x,n,sf);
          

}

int f2(int *v, int x, int inc, int sf)
{
   if(inc+1 == sf){ 
                  if(v[inc] >= x) return inc+1;
                   else if(v[sf] >= x) return sf+1;
                         else return sf+2;

                }

   int n =(sf + inc)/2;
   if(x <= v[n]) return f2(v,x,inc,n);
   else if(x > v[n]) return f2(v,x,n,sf); 
}


int main()
{
 int N, M, i, mod, x, poz;
 FILE *fi, *fo;
 fi = fopen("cautbin.in", "r");
 fo = fopen("cautbin.out", "w");
 fscanf(fi, "%d", &N);
 int *v =(int*)malloc(N*sizeof(int));

 for(i = 0; i < N; i++)
 fscanf(fi, "%d", (v+i));

 fscanf(fi, "%d", &M);
 for(i = 0; i < M; i++)
   {
     fscanf(fi, "%d", &mod);
     fscanf(fi, "%d", &x);
     switch(mod){
     case 0: {
     poz = cautBinara(v, x, 0, N-1);
     if(v[poz - 1] != x) poz = -1;
     fprintf(fo, "%d\n", poz);
     break;
   }
     case 1: {
     
     
     fprintf(fo, "%d\n", cautBinara(v, x, 0, N-1));
     break;
   }
     case 2: {
     
     
     fprintf(fo, "%d\n", f2(v, x, 0, N-1));
       break;
   }
     }
   }
fclose(fi);
fclose(fo);
free(v);
return 0;
}