直接进入正题。

设 $M^x$ 表示进行 $x$ 次 $M$ 操作。

新增操作 $D$，为删除开头结尾两端各一个元素。

如果序列中出现操作 $M^am^bM^c$，且 $a\ge b\land c\ge b$，则这段操作可以被替换为 $M^{a+c-b}D^b$。

关键证明在这里。

可以发现，操作 $M^xD^y$ 与 $D^yM^x$ 等价，也就是 $m$ 或 $M$，与 $D$ 可以任意交换，读者自证不难。

将 $D$ 全部挪至开头，并通过找 $M^am^bM^c$ 将段尽量融合。

以此法调整过后，将序列表示成 $D^\delta M^{a_1} m^{a_2} M^{a_3} m^{a_4}\cdots M^{a_p}$。

一定存在峰 $g$，使得 $\forall 2\le i\le g,a_i>a_{i-2}\land a_i\ge a_{i-1},\forall g\le i \le p-2,a_i>a_{i+2}\land a_i\ge a_{i+1}$。

注意到，$\sum a\in\Theta(n)$，易得 $p\in \Theta(\sqrt{n})$。

也就是说，现在序列的段数很小。

对一个长度为 $n$ 的序列执行操作 $M^x$，使用单调栈容易做到 $\Theta(n)$。

因此，对每一段暴力执行操作，复杂度为 $\Theta(n\sqrt{n})$。

实际常数很小，本地可以通过极限数据。

似乎没有着手卡这个算法的数据，所以时间跑不满，因此目前可以在拿下最短解的同时拿下第二快解。