#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int st,dr,i,v[100001],mij,n,m,q,x;
 int cautare_binara1(int st, int dr,int x)
  {
      while(st<=dr)
      {
          mij=st+(dr-st)/2;
          if(v[mij]==x)
          {
              if(v[mij+1]>x or mij==dr)return mij;
                else
                    st=mij+1;
          }
          else
            if(v[mij]<x) st=mij+1;

            if(v[mij]>x) dr=mij-1;
      }
      return -1;
  }
  int cautare_binara2(int st,int dr,int x)
   {
       int mij;
       while(st<=dr)
       {
          mij=st+(dr-st)/2;
          if(v[mij]<=x)
          {
              if(v[mij+1]>x or mij==dr) return mij;
              else
                st=mij+1;
          }
          else
            dr=mij-1;
       }
   }
   int cautare_binara3(int st,int dr,int x)
     {
         while(st<=dr)
         {
             mij=st+(dr-st)/2;
             if(v[mij]>=x)
             {
                 if(mij==st or v[mij-1]<x) return mij;
                  else
                    dr=mij-1;
             }
             else
                st=mij+1;
         }
     }
int main()
{
    f>>n;
    for(i=1;i<=n;i++)f>>v[i];
    f>>m;
    for(i=1;i<=m;i++){f>>q>>x;
    if(q==0) g<<cautare_binara1(1,n,x)<<"\n";
    if(q==1) g<<cautare_binara2(1,n,x)<<"\n";
    if(q==2) g<<cautare_binara3(1,n,x)<<"\n";
    }
    return 0;
}