#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;
    bool found = false;
    
    if (type == 0) //Daca se cere sa gasim aparitia cea mai spre dreapta a elementului X in array
    {
         mid = min + (max - min)/2;
         if (a[mid]<= val)
         {
              for (int i = mid; i <= max; i++)
              {
                  if (a[i] == val) found = true;
                  if (a[i] > val)
                  {
                       if (found)
                        return i;
                        else return -1;    
                  }
              }       
         }
         else
         {
              for (int i = mid; i >= min; i--)
              {
                  if (a[i] == val) found = true;
                  if (a[i] < val)
                  {
                       if (found)
                        return i;
                        else return -1;    
                  }
              }       
         }
    }
    if (type == 1) //Cea mai mare pozitie pe care se afla un numar mai mic sau egal cu val
    {
         mid = min + (max - min)/2;
         if (a[mid]<= val) //Valoarea se afla pe pozitia curenta sau la dreapta
         {
              for (int i = mid; i <= max; i++)
              {
                  if (a[i] > val)
                  {
                       return i;      
                  }
              }       
         }
         else
         {
              for (int i = mid; i >= min; i--)
              {
                   if (a[i] <= val) return i;
              }       
         }
    }
    if (type == 2) //Cea mai mica pozitie pe care se afla un numar mai mare sau egal cu val
    {
          mid = min + (max - min)/2;
          if (a[mid] < val) //Valoarea se afla pe pozitia curenta sau la dreapta
          {
              for (int i = mid; i <= max; i++)
              {                                 
                  if (a[i] > val)
                  {
                      return i;
                  }
              }       
          }
          else
          {
              for (int i = mid; i >= min; i--)
              {
                   if (a[i] < val) return i + 2;
              }       
          }
    }
}

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;
}