#include<iostream>

using namespace std;

#define INF 0x7fffffff

#define N 10000

// O(n^2)

int len[N];

int dp(int *a, int n){

    int mx = , mxlen = ;

    for (int i = ; i < n; ++i)

        len[i] = ;

    for (int i = ; i < n; ++i){

        mx = ;

        for (int j = ; j < i; ++j)        // 寻找len[0...i-1]最大值

            if (a[j]<a[i] && len[j]>mx)

                mx = len[j];

        len[i] = mx + ;

        if (mxlen < len[i]) mxlen = len[i];    // 更新最大长度

    }

    return mxlen;

}

// O(nlogn)

int mv[N];    //mv[i]存放序列长度为 i+1 的最小元素

int binarySearch(int r, int val)

{

    int left = , right = r, mid;

    while (left < right){

        mid = (left + right) / ;

        if (mv[mid] < val) left = mid + ;

        else right = mid;

    }

    return left;

}

int binaryLIS(int *a, int n)

{

    int len = ;

    mv[] = a[];

    for (int i = ; i < n; ++i){

        if (a[i]>mv[len]) mv[++len] = a[i];

        else mv[binarySearch(len, a[i])] = a[i];

        for (int i = ; i < len; ++i)

            cout << mv[i] << ' ';

        cout << mv[len] << endl;

    }

    return len + ;

}

int main()

{

    int a[] = { , , , , , ,  };

    cout << dp(a, ) << endl;

    cout << binaryLIS(a, ) << endl;

}