#include <stdio.h>

FILE *fin, *fout;
int n, m, a[100001], tip, numar;

int Cauta(int type, int val)
{
    int min = 0, max = n - 1, mid = 0; //low = 0 deoarece index-ul incepe de la 0   
    int retinmid = -1; //<Type = 0> Intreg care retine ultimul mijloc in caz ca s-a gasit elementul cautat (este necesar sa-l gasim pe cel mai
                     // din dreapta astfel ca atunci cand se va descoperi un element mai mare decat valoarea cautata
                     //retinmid va retine pozitia pe care se afla elementul cautat cu un pas inainte)
    bool found = false;
    
    if (type == 0) //Daca se cere sa gasim aparitia cea mai spre dreapta a elementului X in array
    {
          while (min < max) //Cat timp limita de jos este mai mica decat limita de sus
          {
              mid = min + (max - min)/2; //Calculam mijlocul actual
              if (val >= a[mid]) //Daca cumva valoarea cautata este mai mare sau egala cu elementul aflat pe mijlocul actual
              {
                   min++; //Incrementam minimul (avansam spre dreapta in sir)    
                   if (a[mid] == val) { found = true; retinmid = mid; }              
              }
              else
              {
                  
                   max--; //Decrementam maximul  (ne intoarcem spre stanga)
                   if (a[mid] == val) { found = true; retinmid = mid; }      
              }
          }   
          if (found)
          return retinmid + 1;     
          else
          return -1;     
    }
    if (type == 1) //Cea mai mare pozitie pe care se afla un numar mai mic sau egal cu val
    {
          do
          {        
               retinmid = mid;      
               mid = min + (max - min)/2;      
               if (val >= a[mid])
               {
                    min++;                         
               }
               else
               {
                    max--;                        
               }
          } while ((min < max) && (a[mid] <= val));
          return  retinmid + 1;       
    }
    if (type == 2) //Cea mai mica pozitie pe care se afla un numar mai mare sau egal cu val
    {
         do
         {
             retinmid = mid;
             mid = min + (max - min)/2;
             if (val <= a[mid])
             {
                 max--;                        
             }
             else
             {
                 min++;                        
             }
         } while ((min < max) && (a[mid] >= val));   
         return retinmid + 1;      
    }
}

int main()
{
    fin = fopen("cautbin.in", "r");
    fout = fopen("cautbin.out", "w");
    fscanf(fin, "%d", &n);
    for (int i = 0; i < n; i++)
    {
        fscanf(fin, "%d", &a[i]);
    }
    fscanf(fin, "%d", &m);
    for (int i = 0; i < m; i++)
    {
        fscanf(fin, "%d%d", &tip, &numar);
        fprintf(fout, "%d\n", Cauta(tip, numar));
    }
    fclose(fin);          
    fclose(fout);
    return 0;
}