题解通道关了，不知道可不可以发，不能发就删了吧（

一个必要条件：考虑一个更普通的问题，即能否剖分成两个长度没有限制的上升序列。根据 Dilworth 定理可以知道形如 $(i_1,i_2,\cdots,i_k)$ 的满足 $\forall p<k,i_{p}<i_{p+1}\land a_{i_p}\geq a_{i_{p+1}}$ 的链的长度最大是 $2$。

考虑把上面提到的逆序对建一个图，可以发现建成的图一定是一个二分图。那么把二分图每个连通块两部的点的个数跑出来做分组背包即可，最后检查 $f_{n/2}$ 是否为 $1$。

代码也不难写。