#include <fstream>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,m,x,c,st,dr,poz;
int main()
{
    f>>n;
    int v[n+1];
    for(int i=1;i<=n;i++) f>>v[i];
    f>>m;
    for(int i=1;i<=m;i++)
    {
       f>>c>>x;
       if(c==0)
       {
          st=1;
          dr=n;
          poz=0;
          while(st<=dr && poz==0)
          {
             m=(st+dr)/2;
             if(v[m]==x) poz=m;
             else if(v[m]>x) dr=m-1;
             else st=m+1;
             if(poz>0 && v[poz+1]==m)
             {
                poz=0;
                st++;
             }
          }
          while(poz==0)
          {
             x--;
             st=1;
             dr=n;
             while(st<=dr && poz==0)
             {
                m=(st+dr)/2;
                if(v[m]==x) poz=m;
                else if(v[m]>x) dr=m-1;
                else st=m+1;
                if(poz>0 && v[poz+1]==m)
                {
                   poz=0;
                   st++;
                }
             }
          }
          g<<poz;
       }
       else if(c==1)
       {
          st=1;
          dr=n;
          poz=0;
          while(st<=dr)
          {
             m=(st+dr)/2;
             if(v[m]<=x)
             {
                poz=m;
                st=m+1;
             }
             else dr=m-1;
          }
          g<<poz;
       }
       else
       {
          st=1;
          dr=n;
          poz=0;
          while(st<=dr)
          {
             m=(st+dr)/2;
             if(v[m]>=x)
             {
                poz=m;
                dr=m-1;
             }
             else st=m+1;
          }
          g<<poz;
       }
       g<<'\n';
    }
    return 0;
}