#include <fstream>

using namespace std;
long long n,m,v[100001],i,j,poz1,poz2,k,x,y;
int main()
{
    ifstream fin ("cautbin.in");
    ofstream fout ("cautbin.out");
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    for (k=1;k<=m;k++)
    {
        fin>>x>>y;
        if (x==0)
        {
            i=1;
            j=n;
            while (i<=j)
            {
               m=(i+j)/2;
               if (v[m]<=y) i=m+1;
               else j=m-1;
            }
            if (v[m]>y) m--;
            fout<<m<<'\n';
        }
        else if (x==1)
        {
            i=1;
            j=n;
            while (i<=j)
            {
              m=(i+j)/2;
              if (v[m]<=y) i=m+1;
              else j=m-1;
            }
           if (v[m]>y) m--;
           fout<<m<<'\n';
        }
        else
        {
            i=1;j=n;
            while (i<=j)
            {
               m=(i+j)/2;
               if (v[m]<y) i=m+1;
               else j=m-1;
            }
            if (v[m]<y) m++;
            fout<<m<<'\n';
        }
    }
    return 0;
}