#include<fstream.h>

#define xx 100001

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n,m,v[xx];

int main()
{
    fin>>n;
    int i,x,ultim,li,ls,mij,sw;
    
    for(i=1;i<=n;i++)
      fin>>v[i];
    
    fin>>m;
    
    for(;m;m--)
    {
      fin>>i>>x;
      if(i==0)
      {
          for(li=1,ls=n,sw=1;li<=ls && sw;)
          {
             mij=(li+ls)/2;
             if(x<v[mij]) 
                ls=mij-1;
             else
                if(v[mij]<x)
                   li=mij+1;
                else
                   if(v[mij]==x)
                   {
                     fout<<mij<<'\n';
                     sw=0;
                   }
          }
          if(sw==1)
            fout<<"-1\n";
      }
      else
         if(i==1)
         {
                 for(li=1,ls=n;li<=ls;)
                 {
                   mij=(li+ls)/2;
                   if(v[mij]<=x)
                   {
                     ultim=mij;
                     li=mij+1;
                   }
                   else
                     ls=mij-1;
                 }
                 fout<<ultim<<'\n';
         }
         else
            {
                 for(li=1,ls=n;li<=ls;)
                 {
                    mij=(li+ls)/2;
                    if(v[mij]>=x)
                    {
                           ultim=mij;
                           ls=mij-1;
                    }
                    else
                      li=mij+1;
                 }
                 fout<<mij<<'\n';
            }
    }
    
    fout.close();
    return 0;
}