【UR #26】石子合并

喵喵题，要不是由于一些场外原因只想了半个小时的话应该是可以场切的！

首先不难发现，对于最终数组的前后两个数 \(x,y\)，若 \(x>y\)，\(y\) 和 \(x\) 一定位于同一个初始数组内，否则一定是 \(y\) 将 \(x\) 归并到了最终数组内，不合法。

于是我们可以从开头开始找到最终数组的不降子序列。剩下的数一定会作为该子序列内数的附庸存在，不对答案产生贡献。设该子序列为 \(S\)。

剩下的可以归结为一个组合数问题，如果没有【数组非空】的限制，我们是可以随意扔数进数组中的，例如数 \(x\) 在 \(S\) 中出现了 \(3\) 次，通过隔板法，我们便可以得出这部分方案数为 \(C_{n+2}^{n}\)。

加上了该限制的话我们就可以考虑容斥，每次钦定 \(y\) 个数组为空。我们发现组合数式子的每一项是和出现次数相关的，而不同的出现次数最多有 \(O(\sqrt{n})\) 种，故对于每一种出现次数一起算一下，最终时间复杂度即为 \(O(n\sqrt n)\)。

推充要简化问题。