#include<fstream.h>
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,i,nr,m,p,u,intr,x,poz;
int a[100001];
int main()
{f>>n;
 for(i=1 ;i<=n; i++) f>>a[i];
 f>>nr;
 while(nr!=0)
 {f>>intr>>x;
  p=1; u=n; poz=-1;
  if(intr<2)
       {do  {m=(p+u)/2;
              if(a[m]==x)
                  {poz=m; p=m+1;
                   while(p<=u)
                    {m=(p+u)/2;
                     if(a[m]==x) {poz=m; p=m+1;} else u=m-1;
                    }
                  }
                else if(a[m]<x) p=m+1; else u=m-1;
           }
        while(p<=u);
        if(intr==1 && poz==-1) poz=u;
        g<<poz<<'\n';
       }
   else
       {do  {m=(p+u)/2;
             if(a[m]==x)
                  {poz=m; u=m-1;
                   while(p<=u)
                    {m=(p+u)/2;
                     if(a[m]==x) {poz=m; u=m-1;} else p=m+1;
                    }
                  }
                else if(a[m]<x) p=m+1; else u=m-1;
            }   
        while(p<=u);
        if(poz==-1) poz=p;
        g<<poz<<'\n';
       }
  nr--;
 }
 g.close(); return 0;
}