nlogn;

//最长下降子序列，
int operation(int g[])
{
     int len = 0;
    g[0]=2e9;
    for(int i=0;i<n;i++)
    {
        int l=0,r=len;
        if(g[len]>=q[i])g[++len]=q[i];
        else
        {
            while(l<r)
            {
                int mid=l+r>>1;
                if(q[i]>g[mid])r=mid;
                else l=mid+1;
            }
            g[l]=q[i];
            len=max(l,len);
        }
    }
    return len;
}
//最长上升子序列
int operation2(int g[])
{
     int len = 0;
    for (int i = 0; i < n; i ++ )
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (g[mid] < q[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        g[r + 1] = q[i];
    }

    return len;
}