#include <bits/stdc++.h>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
long long a[100001];
int n,m;
int main()
{
   int i,st,dr,mij,x,y;
   fin>>n;
   for(i=1;i<=n;i++)
    fin>>a[i];
   fin>>m;
   for(i=1;i<=m;i++)
   {
       fin>>y>>x;
       if(y==0)
       {
           st=1;
           dr=n;
           int pozmax=0;
           while(st<=dr)
           {
               mij=(st+dr)/2;
               if(a[mij]==x)
               {
                   pozmax=mij;
                   st=mij+1;
               }
               else if (a[mij]<x)
                st=mij+1;
               else
                dr=mij-1;

           }
           fout<<pozmax<<"\n";
       }
      else if(y==1)
      {
          dr=n;
          st=1;
          int pozmax=0;
          while(st<=dr)
          {
              mij=(st+dr)/2;
              if(a[mij]<=x)
              {
                  pozmax=mij;
                  st=mij+1;
              }
              else dr=mij-1;
          }
          fout<<pozmax<<"\n";
      }
      else
      {
          dr=n;
          st=1;
          int pozmax=0;
          while(st<=dr)
          {
              mij=(st+dr)/2;
              if(a[mij]>=x)
              {
                  pozmax=mij;
                  dr=mij-1;
              }
              else st=mij+1;
          }
          fout<<pozmax<<"\n";
      }
   }


}