#include <fstream>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int y,n,a[100005],x,i,k,m;
int c0(int st,int dr)
{
    int mij;
    if(st<=dr)
      {mij=(st+dr)/2;
       if(a[mij]==x)
         {
             y=mij;
             return c0(mij+1,dr);
         }
        else {if(a[mij]<x)
                return c0(mij+1,dr);
              else return c0(st,mij-1);  }
      }
      return y;
}

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

      }
      return y;
}

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

      }
      return y;
}

int main()
{
    f>>n;
    for(i=1;i<=n;i++)
      f>>a[i];
    f>>m;
    for(i=1;i<=m;i++)
      {f>>k;
      y=-1;
       if(k==0)
         {
             f>>x;
             g<<c0(1,n)<<'\n';

         }
       else if(k==1)
       {
           f>>x;
           g<<c1(1,n)<<'\n';
       }
       else{f>>x;
       g<<c2(1,n)<<'\n';}  }
    f.close();
    g.close();
    return 0;
}