$\mathbf{Part. -1}$

翻译自 ROI 2023 D1T3。

如果对于所有 $1 \le j < i$，都有 $a_j < a_i$，则称 $a_i$ 为峰值。

如果对于所有 $1 \le j < i$，都有 $a_j > a_i$，则称 $a_i$ 为反峰值。

给定大小为 $n$ 的排列 $p_1,p_2,\dots,p_n$。需要将其分为两个非空子序列 $q$ 和 $r$。每个元素 $p$ 必须恰好被分到一个子序列中。你需要最大化 $q$ 中的峰值数量和 $r$ 中的反峰值数量之和。

$1 \leq n \leq 2 \times 10^5$。

$\mathbf{Part. 1}$

我们按顺序考虑每一个 $a_i$。由于我们要把序列划分成两个子序列，分别是前缀最大和前缀最小，所以我们定义 $mx$ 表示当前考虑到第 $i$ 个数的前缀最大序列中最后一个值，$mn$ 表示当前考虑到第 $i$ 个数的前缀最小序列中最后一个值。显然，我们可以通过储存这两个值来进行 DP。设 $f_{i, mx, mn}$ 表示当前考虑到第 $i$ 个数的 $mx$ 和 $mn$ 值，则转移是朴素的。

我们想要更快的算法，于是我们考虑研究 DP 转移的过程（也是按顺序对 $a_i$ 分配的过程）。对于每一个数 $a_i$，当前的 $mx,mn$ 我们已经知道了：

• 对于 $mx < mn$ 来说：
  • 如果 $mx < mn < a_i$，则我们将 $a_i$ 加到 $mx$ 数列里会更新，加到 $mn$ 数列里没影响。
  • 如果 $a_i < mx < mn$，则我们将 $a_i$ 加到 $mx$ 数列里没影响，加到 $mn$ 数列里会更新。
  • 如果 $mx < a_i < mn$，则加到任何一个数列都会更新。$^{{\color{red}(1)}}$
• 对于 $mn < mx$ 来说：
  • 如果 $mn < mx < a_i$，则我们将 $a_i$ 加到 $mx$ 数列里会更新，加到 $mn$ 数列里没影响。
  • 如果 $a_i < mn < mx$，则我们将 $a_i$ 加到 $mx$ 数列里没影响，加到 $mn$ 数列里会更新。
  • 如果 $mn < a_i < mx$，则加到任何一个数列都没有影响。

对于两种情况，显然只有 $a_i$ 在中间的时候情况不同。似乎如果更新少一点更简单，所以我们考虑 $mn < mx$。

$\mathbf{Part. 2}$

我们考虑 $mn < mx$。对于这种情况，我们发现，对于每个数，如果它可以但是不用在 $mx$ 或者 $mn$ 数列中的话，它可以选择不影响答案。因此，对于所有后面 $> mx$ 的数，我可以选择一些来构成最长上升子序列，其他的划分到 $mn$ 去，不对答案造成影响。$< mn$ 的数同理$^{\color{red}(2)}$。容易发现，这其实是 $\mathbf{LIS}$ 和 $\mathbf{LCS}$ 问题，而这个问题我们可以用 $\mathbf{BIT}$ 轻松计算出每个 $a_i$ 开头的 $\mathbf{LIS,LCS}$ 值。

但是对于 $mx < mn$，由于 $\color{red}(1)$ 的存在，并不是每个数都能选择不影响序列。如果我们直接考虑研究 $mx < mn$ 的转移过程，那是没有任何性质的$^{\color{red}(3)}$。但是，如果我们观察答案整体的结构，我们发现 $mx > mn$ 和 $mn > mx$ 分别是这个序列中的前缀和后缀部分，所以不难想到枚举分界点。

（为了方便区分，我们后文将 $mx < mn$ 的部分称为前面的部分，$mx < mx$ 的部分称为后面的部分）

我们考虑枚举分界点 $x$。如果我们要求后面的部分，它的答案，那么由 $\color{red}(2)$，我们需要知道 $mn$ 和 $mx$ 的值来划分后面的数分别可以分到哪一个数列。因此，我们考虑枚举在分界点 $x$ 选择完之后，$mn,mx$ 的值的。（此时，$mn < mx$）

接着，我们考虑前面的部分怎么求。首先，由 $\color{red}(3)$，前面的操作过程没什么救，但是我们知道前面 $mx < mn$ 啊！由于所有 $mx$ 序列的所有数都 $\leq mx$，$mn$ 序列的所有数都 $\geq mn$，而 $mx <mn$，所以 $mx$ 序列的所有值都小于 $mn$ 序列的所有值！因此，我们再考虑枚举分界点 $x$ 还没选择前，$mn,mx$ 的值。这样，我们可以预处理出前面所有 $\leq mx$ 的数的前缀最大值个数，和所有 $\geq mn$ 的前缀最小值的个数。

当然，实际上你在枚举 $mn,mx$ 的时候，有可能存在 $a_i$，使得 $mx < a_i < mn$。这种情况显然不合法！因此，我们枚举的 $mx$ 和 $mn$ 需要保证不存在 $a_i$ 使得 $mx < a_i < mn^{\color{red}{(4)}}$。

但这样复杂度直接起飞，非常不好。考虑我们都枚举了什么东西。

• 分界点 $x$
• 分界点选择之前 $mx,mn$ 值
• 分界点选择之后 $mx,mn$ 值

我们发现，分界点选择之前的 $mx,mn$ 和之后的 $mx,mn$ 肯定有很多重复啊！假设 $x$ 选择之前是 $mx,mn$，那 $x$ 选择，肯定要么更新 $mx$，要么更新 $mn$，然后都是变成 $a_x$，所以实际上我们只需要枚举 $mx,mn$，然后分类讨论一下即可。

我们明明已经找到了这么多性质，时间复杂度还是 $\mathcal{O}(n^3)$。怎么回事呢？但其实不然。由 $\color{red}(4)$，我们知道 $mx,mn$ 肯定是前面的 $a_i$ 的值，而我们不能存在 $a_i$ 在 $mx,mn$ 之间，所以实际上 $mx$ 是 $mn$ 的后继。因此，你只需要枚举 $mx,x$ 两个值即可，复杂度为 $\mathcal{O}(n^2)$。

我们考虑这个算法的细节。首先，枚举 $x,mx$，则 $mn$ 是很容易通过维护 $\mathbf{set}$ 算出来的。然后，我们发现对于一个 $mx$，肯定在前面出现过，而且这个 $mx$ 后面的数是没用的，所以我们可以对于每个 $a_i \leq mx$，预处理出所有 $\leq mx$ 的数的前缀最大值个数，$mn$ 同理。对于后面的部分，我们可以通过 $\mathbf{BIT}$，求出以每个 $a_i$ 为开头的 $\mathbf{LIS,LCS}$。然后，由于我们要求以 $x$ 为开头的最长子序列，和以 $i > x,a_i < mn$ 或者 $i > x, a_i > mx$ 开头的最长子序列，因此我们按顺序扫一下 $mx$ 就可以快速求出。

$\mathbf{Part. 3}$

我们考虑优化这个算法。

我们大概的思路是：枚举一个值，另一个值数据结构维护，所以我们可以枚举 $x$。结果我们发现，枚举 $x$ 完全不可做！！！？？？这怎么办？

我们考虑枚举 $x$ 为什么不优秀。枚举 $x$，给我们提供了 $mx < mn < a_x$ 或 $a_x < mx < mn$ 的信息，让我们知道从 $i$ 开始进入后面的部分，但是我们不知道 $mx,mn$；不知道 $mn$ 后面应该找什么数（这里就很离谱了：我们不知道 $mn$，还要对于 $x > i,a_x < mn$ 来二维数点！），但是知道 $mx$ 后面一定是 $i$。如果枚举 $mx$ 的话，如果 $mn$ 在 $mx$ 的右边，那我们不能知道 $mn$ 是什么。

我们对于 $mx,mn$ 维护的信息是不平衡的，但是我们又要通过 $mx$ 求出来 $mn$。于是，我们应该要枚举一个点，这个点左边涵盖了 $mn,mx$，右边是我们要找的转折点 $x$。如果 $mx$ 在 $mn$ 左边，这个 $x$ 可以是 $mx$，否则可以是 $mn$……对！我们可以枚举 $mn$ 和 $mx$ 最靠右的那个点！

假设我们枚举了 $x$，其中 $mn,mx$ 都在 $x$ 左边，且其中有一个是 $a_x$。由 $\color{red}(4)$，这两个值在 $x$ 左边的值域上肯定是相邻的，所以我们可以通过 $mx$ 求出来另一个 $mn$。那么，我们分类讨论 $x$ 是 $mx$ 还是 $mn$，对于每种情况，我们还要考虑是 $mn$ 还是 $mx$ 的更新造成了 $mn,mx$ 的大小关系变化。因此，我们枚举 $x$，然后分类讨论四种情况。不妨设 $a_x$ 是 $mx$，我们算出来了 $mn$，$mx$ 跳完后超过了 $mn$，则跳的下标 $p$ 要满足 $p > x, a_p > mn$，然后求 $\mathbf{LIS}(p)$ 的最大值，这是经典的二位数点。

$\mathbf{Part. +\infin}$

这份代码是 @Albert_Wei 写的，本人还没写，写了 update。

int n, p[N], res[N][2], l[N], r[N];

struct BIT {
    int tr[N];
    void init() { F(i, 1, n + 1) tr[i] = 0; }
    void modify(int x, int y) { for (; x <= n + 1; x += (x & -x)) tr[x] += y; }
    int query(int x) { int ans = 0; for (; x; x -= (x & -x)) ans += tr[x]; return ans; }
} S;
struct BIT2 {
    int tr[N];
    void init() { F(i, 1, n) tr[i] = 0; }
    void modify(int x, int y) { for (; x <= n; x += (x & -x)) Fmax(tr[x], y); }
    int query(int x) { int ans = 0; for (; x; x -= (x & -x)) Fmax(ans, tr[x]); return ans; }
} U, V;

void solve() {
    n = read();
    F(i, 1, n) p[i] = read();
    S.init();
    set<int> st;
    st.insert(0), st.insert(n + 1);
    F(i, 1, n) {
        l[i] = *(-- st.lower_bound(p[i])), r[i] = *st.upper_bound(p[i]);
        S.modify(l[i] + 1, 1), S.modify(r[i] + 1, -1);
        res[i][0] = S.query(p[i] + 1), res[i][1] = S.query(p[i]), st.insert(p[i]);
    }
    int ans = 0;
    U.init(), V.init();
    G(i, n, 1) {
        if (r[i] != n + 1) Fmax(ans, res[i][0] + U.query(n - r[i]) + V.query(r[i]));
        Fmax(ans, res[i][0] + U.query(n - p[i]) + V.query(p[i]));
        Fmax(ans, res[i][1] + U.query(n - p[i]) + V.query(p[i]));
        if (l[i]) Fmax(ans, res[i][1] + U.query(n - l[i]) + V.query(l[i]));
        U.modify(n - p[i] + 1, U.query(n - p[i]) + 1);
        V.modify(p[i], V.query(p[i]) + 1);
    }
    F(i, 0, n) Fmax(ans, U.query(n - i) + V.query(i));
    cout << ans << '\n';
}