题目重述

称一个整数序列是美丽的，如果满足：

• 除第一个元素外，每个元素左边都存在一个比它小的元素；
• 除最后一个元素外，每个元素右边都存在一个比它大的元素。

给定数组 $a$，求最长美丽子序列的长度。

性质转化

美丽序列的定义等价于：

序列的第一个元素是唯一的最小值，最后一个元素是唯一的最大值。

原因：

• 第一个元素左边没有元素，所以它必须是整个序列的最小值（否则它左边无法有比它小的元素）。
• 最后一个元素右边没有元素，所以它必须是整个序列的最大值（否则它右边无法有比它大的元素）。
• 中间元素满足左右各有比它小和比它大的元素，自然可以满足条件。

因此，问题转化为：在数组 $a$ 中找最长子序列，使得第一个元素是子序列的最小值（且唯一），最后一个元素是子序列的最大值（且唯一）。

二维平面转化

将每个元素 $a_i$ 视为平面上的点 $(i, a_i)$。

一个美丽子序列对应一个矩形：
设子序列的第一个元素下标为 $i$，最后一个元素下标为 $j$（$i < j$），且 $a_i < a_j$（否则无法成为最小和最大）。
那么子序列可以包含所有满足 $i \le p \le j$ 且 $a_i < a_p < a_j$ 的点吗？
实际上，我们可以在矩形内自由选择中间的点，只要保持单调性要求即可。

关键观察：
如果我们固定左下角 $(i, a_i)$ 和右上角 $(j, a_j)$，那么所有严格位于矩形内部的点 $(p, a_p)$ 满足 $i < p < j$ 且 $a_i < a_p < a_j$。这些点可以任意排列成美丽子序列（按原顺序），而两端 $(i, a_i)$ 和 $(j, a_j)$ 恰好是最小和最大。
所以，以 $i$ 为起点、$j$ 为终点的美丽子序列的最大长度等于矩形内部点数 $+ 2$（包含两端）。

因此问题变成：找两个点 $(i, a_i)$ 和 $(j, a_j)$（$i < j, a_i < a_j$），使得矩形 $(i, a_i)$ 到 $(j, a_j)$ 内部包含尽可能多的点。

优化起点和终点

起点优化

如果存在 $i' < i$ 且 $a_{i'} \le a_i$，那么以 $i'$ 为起点的矩形可以包含以 $i$ 为起点的矩形（因为 $i'$ 更左，$a_{i'}$ 更小或相等，矩形更大），所以答案不会更差。
因此我们只需要考虑前缀最小值点：$i$ 满足对所有 $i' < i$，有 $a_{i'} > a_i$。
这些点满足：下标递增，值严格递减。记这些点为 $left$ 数组。

终点优化

对称地，只需要考虑后缀最大值点：$j$ 满足对所有 $j' > j$，有 $a_{j'} < a_j$。
这些点满足：下标递增，值严格递增。

矩形匹配

对于任意点 $x$（作为候选终点），哪些 $left$ 中的点可以作为它的左下角？
需要满足：

1. 下标 $i < x$（否则不是左下角）
2. 值 $a_i < a_x$（否则不能是最小值）

由于 $left$ 下标递增、值递减，所以满足 $a_i < a_x$ 的 $i$ 是 $left$ 中一个前缀，满足下标 $i < x$ 的是另一个前缀。
取交集，得到 $left$ 中连续的一段区间 $[\text{lf}, \text{rg})$，其中：

• $\text{lf}$ 是第一个满足 $a_{\text{left}[\text{lf}]} < a_x$ 的位置
• $\text{rg}$ 是第一个满足 $\text{left}[\text{rg}] \ge x$ 的位置

这两个边界都可以用二分查找在 $O(\log n)$ 时间内得到。

算法流程

我们考虑从右到左枚举终点 $j$（只枚举后缀最大值点）。
维护一个数据结构，对于每个 $left$ 中的起点 $i$，记录当前有多少个已加入的点位于矩形 $(i, a_i)$ 到当前终点 $j$ 的内部。

当我们从 $j$ 移动到下一个更左的终点 $j'$（$j' < j$）时：

• 新加入的终点 $j'$ 值更大（因为后缀最大值递增），所以需要把值介于 $a_j$ 和 $a_{j'}$ 之间的点加入数据结构。
• 同时，下标在 $[j', j)$ 之间的点被排除（因为新的矩形左边界右移了，这些点不再在内部）。

每个点只会被加入一次、删除一次，所以总操作次数 $O(n)$。

数据结构需要支持：

• 区间加（给某个起点对应的所有矩形内部点数加 $1$ 或减 $1$）
• 查询全局最大值

这可以用线段树维护区间加和区间最大值。

最终答案

对于每个候选终点 $j$，查询 $left$ 中区间 $[\text{lf}_j, \text{rg}_j)$ 的最大值，记为 $m$。
则该终点对应的最长美丽子序列长度为 $m + 1$（加上终点自身）。
注意：如果区间为空，则只能单独取该点，长度为 $1$。

取所有候选终点的最大值即为答案。

时间复杂度：$O(n \log n)$。