RT，萌新有了一个 $O(n\log n)$ 的做法。

首先，判断原序列是否可以分成两个单增的序列。这个求一下最长非升子序列即可。

然后，判断每个点是否可以被一个长度至少为 $\frac{n}{2}$ 的上升子序列包含。这个求两遍 LIS 即可。

这两步的复杂度都是 $O(n\log n)$ 的。

萌新感觉很假，但是又叉不掉。

注：所有 $n\le 6$ 的数据都已经测过了

求一个证明或者hack

代码二楼