还是注意到 $1, 3$ 的选择必然是前后缀的性质。我们写出暴力并 观察数据 打表发现，在可以合法的情况下（就是不选任何 $\texttt{321}$ 的情况下，如果可以合法），我们会尽量多选 $\texttt{123}$，这是优的。所以直接二分 $\texttt{123}$ pattern 的数量，二分出来后再二分 $\texttt{321}$ 的数量，即可。check 容易做到线性。总复杂度 $O(n \log n)$。

第一遍二分我们可以直接贪心选择每个 $1$ 后面第一个 $2$，然后可以算出这个 $1$ 匹配的 $3$ 的限制，这样可以算出最多选择多少个 $\texttt{123}$，以此做到线性。

第二遍二分还不会优化。

这个结论为什么是对的我也不知道。