#include <iostream>
#include <fstream>
using namespace std;
long a[100001],n,poz,k;
long n0(long x,long st, long dr)
   {
       if(st<=dr)
         {
             poz=(st+dr)/2;
             if(a[poz]>x)
                return n0(x,st,poz-1);
                else
             if(a[poz]<x)
                return n0(x,poz+1,dr);
                else
                {
                   while(a[poz]==x)
                     poz++;
                   return poz-1;
                }
         }
        return -1;
   }
long n1(long x,long st, long dr)
   {
       while(st<=dr)
         {
             poz=(st+dr)/2;
             if(a[poz]<=x)
               {
                   k=poz;
                   st=poz+1;
               }
               else
               dr=poz-1;

         }
       return k;
   }
long n2(long x,long st, long dr)
   {
       if(st<=dr)
         {
             poz=(st+dr)/2;
             if(a[poz]>x)
                return n2(x,st,poz-1);
                else
             if(a[poz]<x)
                return n2(x,poz+1,dr);
                else
                {
                    while(a[poz]==x)
                       poz--;
                    return poz+1;
                }

            if(a[poz]<x)
               return poz+1;
               else
               return poz;
         }


   }

int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    long n,m,i,x,y;
    f>>n;
    for(i=1;i<=n;i++)
      f>>a[i];
    f>>m;
    for(i=1;i<=m;i++)
      {
          f>>x>>y;
          if(x==0)
            g<<n0(y,1,n)<<'\n';
            else
          if(x==1)
                g<<n1(y,1,n)<<'\n';
            else
            g<<n2(y,1,n)<<'\n';

      }
    f.close();
    g.close();
    return 0;
}