#include <fstream>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int n , a[100009], i , t, val, cer;

int cer0(int val)
{
    int st=1,dr=n;
      int mj,rez=-1;
      while(st<=dr)
      {
          mj=(st+dr)/2;
            if (a[mj]==val)
               {st=mj+1;
               rez=mj;
               }
               else
               if(a[mj]>val)
               dr=mj-1;
               else
                 st=mj+1;
      }
    return rez;
}
int cer1(int val)
{
    int st=1,dr=n;
      int mj,rez=0;
       while(st<=dr)
       {
           mj=(st+dr)/2;
           if(a[mj]<=val)
            {
                st=mj+1;
                rez=mj;
            }
            else
            dr=mj-1;
       }
    return rez;
}
int cer2(int val)
{
    int st=1,dr=n;
     int mj,rez;
       while(st<=dr)
       {
           mj=(st+dr)/2;
             if (a[mj]>=val)
             {
                 rez=mj;
                 dr=mj-1;
             }
             else
              st=mj+1;
       }
       return rez;
}
int main()
{
   f >> n ;
      for ( i = 1 ; i <= n ; i ++ )
         f >> a[i];
        f >> t;
        while(t--)
        {
            f >> cer >> val;
            if (cer==0)
              g <<cer0(val)<<'\n';
               else
                if (cer==1)
                     g << cer1(val)<<'\n';
                 else
                       g << cer2(val)<<'\n';
        }
    return 0;
}