线性 DP：最长上升子序列

// 最长上升子序列 —— 2ⁿ 枚举子集（对拍的标准答案）
//
// 题意：给一个长度为 n 的序列，从中**按原顺序**挑出若干个数（可以不连续），
//       要求挑出来的这些数**严格递增**。最多能挑几个？
//
//   例：2 5 3 7 1 → 最多挑 3 个（2 5 7，或者 2 3 7）
//
// ⚠ 「子序列」不是「子串」：子串必须连着，子序列只要保持先后顺序就行。
//    这两个字是很多人做这题的第一个坑。
//
// 这份代码没有任何想法：n 个数每个「选或不选」，2ⁿ 种组合全试一遍
// （二进制枚举，接第 3 章），检查选出来的是不是严格递增，取最长的。
//
// 它慢得离谱（n = 25 就要跑几秒），但它**绝对不会错** ——
// 后面两种 DP 写法都要拿它来验。
//
// 输入：第一行 n，第二行 n 个整数
// 输出：最长上升子序列的长度

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int best = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        int cnt = 0;
        long long last = LLONG_MIN;
        bool ok = true;
        for (int i = 0; i < n && ok; i++) {
            if (!(mask >> i & 1)) continue;
            if (a[i] <= last) ok = false;      // 严格递增：等于也不行
            else { last = a[i]; cnt++; }
        }
        if (ok) best = max(best, cnt);
    }

    cout << best << "\n";
    return 0;
}

// 最长上升子序列 —— O(n²) DP：这一章真正要学的状态设法
//
// ============ DP 三件套（第 21 章立的规矩） ============
//
//   【状态】f[i] = **以 a[i] 结尾**的最长上升子序列长度
//
//     ★ 为什么要加「以 a[i] 结尾」这五个字？
//       如果状态设成「前 i 个数里的最长上升子序列长度」，你会发现转移写不出来 ——
//       因为你不知道那个最长子序列的**结尾是多少**，也就没法判断 a[i] 能不能接上去。
//       状态里必须留下「接下来能不能接」所需要的信息，这叫**无后效性**。
//       「以 i 结尾」是 DP 里最常用的一种补救办法，见到「子序列 / 子段」类题目先试它。
//
//   【转移】f[i] = 1 + max{ f[j] : j < i 且 a[j] < a[i] }（没有这样的 j 就是 1）
//       —— 还是那句万能问法：**倒数第二个数是谁？** 枚举它就行。
//
//   【边界和顺序】每个 f[i] 至少是 1（就它自己）；i 从小到大填，
//       因为 f[i] 只依赖下标更小的 f[j]。**依赖谁，就先填谁。**
//
//   【答案】max(f[0..n-1])。
//       ⚠ 不是 f[n-1]！最长的那条不一定以最后一个数结尾。这是这题第二个坑。
//
// 复杂度 O(n²)：n = 5000 完全没问题（洛谷 B3637 就是这个数据范围）。
// n 到 10⁵ 才需要下一份 fast.cpp 的 O(n log n)。
//
// 输入输出和 brute.cpp 一样。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<int> f(n, 1);            // 边界：每个数自己就是一个长度为 1 的上升子序列
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++)
            if (a[j] < a[i])                    // 严格上升，写 <= 就变成「非降」了（见 dup.cpp）
                f[i] = max(f[i], f[j] + 1);
        ans = max(ans, f[i]);                   // 答案是所有 f[i] 里最大的
    }

    cout << ans << "\n";
    return 0;
}

// 最长上升子序列 —— O(n log n)：tails 数组 + 二分
//
// ★ 关键的一步，一句话：
//
//   tails[k] = **所有长度为 k+1 的上升子序列里，结尾最小的那个结尾值**
//
//   为什么要「结尾最小」：结尾越小，后面越容易接上新的数。
//   同样长度的子序列，我们只关心最好接的那一个 —— 别的都可以扔掉。
//
// ★ 第二步（这才是能二分的理由）：**tails 一定是严格递增的。**
//
//   反证一下：如果 tails[k] >= tails[k+1]，那么那个长度为 k+2、结尾是 tails[k+1] 的子序列，
//   把它的最后一个数去掉，就得到一个长度为 k+1、结尾 < tails[k+1] <= tails[k] 的子序列 ——
//   比 tails[k] 还小，和「tails[k] 是最小结尾」矛盾。
//
//   所以 tails 天然单调，**可以二分**（第 8 章的 lower_bound 在这里派上用场）。
//
// 于是扫描每个 a[i]，在 tails 里找第一个 >= a[i] 的位置 p：
//   - 找不到（a[i] 比所有都大）→ 直接接到末尾，最长长度 +1
//   - 找到了 → 用 a[i] 把 tails[p] 换掉（同样长度，换一个更小的结尾，以后更好接）
// 答案就是 tails 的长度。
//
// ⚠⚠ 最容易产生的误解，这一章会反复强调：
//     **tails 数组不是那条最长上升子序列本身！**
//     它只是「每种长度的最好结尾」的记录板，中途会被改得面目全非。
//     序列 2 5 3 7 1 跑完之后 tails = [1, 3, 7]，而 1 在原序列里排在 7 的**后面** ——
//     [1,3,7] 根本不是原序列的子序列。但它的**长度 3 是对的**。
//     真要输出那条序列，得像 path.cpp 那样另外记前驱。
//
// 这里手写二分（接第 8 章），stl.cpp 里有用 std::lower_bound 的等价写法。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<long long> tails;                 // tails[k]：长度 k+1 的上升子序列的最小结尾
    for (int i = 0; i < n; i++) {
        // 手写 lower_bound：找第一个 >= a[i] 的位置（第 8 章的模板）
        int l = 0, r = (int)tails.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (tails[mid] >= a[i]) r = mid;
            else l = mid + 1;
        }
        if (l == (int)tails.size()) tails.push_back(a[i]);   // 比所有都大，接到末尾
        else tails[l] = a[i];                                 // 否则换掉那一格
    }

    cout << tails.size() << "\n";
    return 0;
}

// 最长上升子序列 —— 不只要长度，还要**把那条序列本身还原出来**
//
// 为什么要有这份代码：
// tails 那套写法只能给你长度（原因见 fast.cpp 和 trace.cpp 里的警告）。
// 题目一旦要求输出方案，就得回到 O(n²) 的 f[i]，并且**记住每一步是从谁转移过来的**。
//
// ★ 还原方案的通用套路（所有 DP 都一样，不止这题）：
//   转移的时候顺手记一个 pre[i] = 「f[i] 是从哪个 j 转移来的」；
//   最后从最优的那个下标出发，顺着 pre 一路往回走，走出来的就是方案（记得倒过来）。
//
// 这个套路在背包（第 23 章）、区间 DP（第 26 章）里会原样再用一遍。
//
// 输出：第一行长度，第二行那条上升子序列（长度相同的答案可能有多条，这里给字典序最靠前找到的那条）
//
// 顺带一提：这份代码同时也是 check-viz 的一个「硬验证」——
// 脚本会检查它输出的序列**真的是原序列的子序列、真的严格递增、长度真的等于答案**。
// 只对长度不对方案的话，这种错误对拍是抓不出来的。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    if (n == 0) { cout << 0 << "\n\n"; return 0; }

    vector<int> f(n, 1), pre(n, -1);
    int best = 1, bestAt = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && f[j] + 1 > f[i]) {
                f[i] = f[j] + 1;
                pre[i] = j;                     // ★ 记住是从谁接过来的
            }
        }
        if (f[i] > best) { best = f[i]; bestAt = i; }
    }

    vector<long long> path;
    for (int i = bestAt; i != -1; i = pre[i]) path.push_back(a[i]);
    reverse(path.begin(), path.end());          // 顺着 pre 走出来是倒的

    cout << best << "\n";
    for (size_t i = 0; i < path.size(); i++) cout << path[i] << " \n"[i + 1 == path.size()];
    return 0;
}

// 最长上升子序列 —— 「严格上升」和「非降」只差一个字母，答案差很多
//
// 这是 LIS 这题最经典的坑，而且**只有在有重复元素的数据上才会暴露**：
//
//     严格上升（strictly increasing）：a < b，相等不行 → 用 lower_bound
//     非降    （non-decreasing）    ：a <= b，相等可以 → 用 upper_bound
//
// 一个字母的差别。而题面里那句话可能是「严格递增」「单调不减」「不下降」——
// **先把题读准，再决定用哪个**。
//
// 这份代码把两种都跑一遍，并排打给你看。默认数据 1 3 3 3 5 里：
//     严格上升最长 3（1 3 5），非降最长 5（1 3 3 3 5）。
//
// 顺便再说一个第 8 章的老坑：lower_bound / upper_bound 的名字很容易记反。
//     lower_bound(x) = 第一个 **>= x** 的位置
//     upper_bound(x) = 第一个 **>  x** 的位置
// 记不住就现场造一个「有重复元素」的小例子试一下 —— 三十秒的事，比背可靠。
//
// 输入输出格式和 brute.cpp 一样，输出是两行对比。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<long long> t1;                      // 严格上升
    for (long long x : a) {
        auto it = lower_bound(t1.begin(), t1.end(), x);
        if (it == t1.end()) t1.push_back(x); else *it = x;
    }

    vector<long long> t2;                      // 非降
    for (long long x : a) {
        auto it = upper_bound(t2.begin(), t2.end(), x);
        if (it == t2.end()) t2.push_back(x); else *it = x;
    }

    cout << "严格上升（lower_bound）：" << t1.size() << "\n";
    cout << "非降  （upper_bound）：" << t2.size() << "\n";
    cout << (t1.size() == t2.size()
                 ? "这组数据上两者相等 —— 说明它里面没有「能派上用场的重复元素」，换一组带重复的再试。\n"
                 : "两者不同。差别全部来自重复元素：非降允许把相等的数接在一起。\n");
    return 0;
}

// 最长上升子序列 —— O(n log n)：tails 数组 + 二分
//
// ★ 关键的一步，一句话：
//
//   tails[k] = **所有长度为 k+1 的上升子序列里，结尾最小的那个结尾值**
//
//   为什么要「结尾最小」：结尾越小，后面越容易接上新的数。
//   同样长度的子序列，我们只关心最好接的那一个 —— 别的都可以扔掉。
//
// ★ 第二步（这才是能二分的理由）：**tails 一定是严格递增的。**
//
//   反证一下：如果 tails[k] >= tails[k+1]，那么那个长度为 k+2、结尾是 tails[k+1] 的子序列，
//   把它的最后一个数去掉，就得到一个长度为 k+1、结尾 < tails[k+1] <= tails[k] 的子序列 ——
//   比 tails[k] 还小，和「tails[k] 是最小结尾」矛盾。
//
//   所以 tails 天然单调，**可以二分**（第 8 章的 lower_bound 在这里派上用场）。
//
// 于是扫描每个 a[i]，在 tails 里找第一个 >= a[i] 的位置 p：
//   - 找不到（a[i] 比所有都大）→ 直接接到末尾，最长长度 +1
//   - 找到了 → 用 a[i] 把 tails[p] 换掉（同样长度，换一个更小的结尾，以后更好接）
// 答案就是 tails 的长度。
//
// ⚠⚠ 最容易产生的误解，这一章会反复强调：
//     **tails 数组不是那条最长上升子序列本身！**
//     它只是「每种长度的最好结尾」的记录板，中途会被改得面目全非。
//     序列 2 5 3 7 1 跑完之后 tails = [1, 3, 7]，而 1 在原序列里排在 7 的**后面** ——
//     [1,3,7] 根本不是原序列的子序列。但它的**长度 3 是对的**。
//     真要输出那条序列，得像 path.cpp 那样另外记前驱。
//
// 这里手写二分（接第 8 章），stl.cpp 里有用 std::lower_bound 的等价写法。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<long long> tails;                 // tails[k]：长度 k+1 的上升子序列的最小结尾
    for (int i = 0; i < n; i++) {
        // 手写 lower_bound：找第一个 >= a[i] 的位置（第 8 章的模板）
        int l = 0, r = (int)tails.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (tails[mid] >= a[i]) r = mid;
            else l = mid + 1;
        }
        if (l == (int)tails.size()) tails.push_back(a[i]);   // 比所有都大，接到末尾
        else tails[l] = a[i];                                 // 否则换掉那一格
    }

    cout << tails.size() << "\n";
    return 0;
}