#include <stdio.h>
#define max 100010

int a[max], n, m, t, x;


int binary_search1(int x)
{
  int st, dr, mij;
  st = 1; dr = n;
   while(st <= dr)
    {
      mij = st + (dr-st)/2;
       if(a[mij] == x)
         return mij;
      else
       if(a[mij] < x)
        st = mij + 1;
      else
        dr = mij - 1;
    }
   return -1;
}


int binary_search2(int x)
{
  int st, dr, mij, sol = 0;
  st = 1; dr = n;
    while(st <= dr)
     {
       mij = st + (dr-st)/2;
        if(a[mij] <= x)
         {
           sol = mij;
           st = mij + 1;
         }
       else
         dr = mij - 1;
     }
  return sol;
}


int binary_search3(int x)
{
  int st, dr, mij, sol = n+1;
   st = 1; dr = n;
     while(st <= dr)
      {
        mij = st + (dr-st)/2;
         if(x <= a[mij])
          {
            sol = mij;
            dr = mij - 1;
          }
        else
          st = mij + 1;
      }
   return sol;
}


int main()
{
  freopen("cautbin.in" , "r" , stdin);
  freopen("cautbin.out" , "w" , stdout);
    scanf("%d" , &n);
      for(int i = 1 ; i <= n ; i++)
        scanf("%d " , &a[i]);
    scanf("%d" , &m);
     for(int i = 1 ; i <= m ; i++)
      {
        scanf("%d %d", &t, &x);
          if(t == 0)
            printf("%d\n" , binary_search1(x));
        else
          if(t == 1)
            printf("%d\n" , binary_search2(x));
        else
           printf("%d\n" , binary_search3(x));
      }
   fclose(stdin);
   fclose(stdout);
  return 0;
}