题解

思路

对排列 $Q$，设前 $k$ 个位置已经满足 $Q_i=i$。

做法

若 $k=N$，它已经是字典序最小的排列，最优操作不会改变它；否则数字 $k+1$ 必定出现在后方，把从位置 $k+1$ 到该数字所在位置的区间反转，能够让正确前缀增长，而任何不能做到这一点的反转所得排列都更大，所以最优反转唯一由这个位置决定。

反过来计数。设 $K$ 是 $P$ 的最长正确前缀长度。通过反转 $P$ 的区间 $[l,r]$ 构造出的 $Q$ 能以该区间作为最优反转还原为 $P$，恰好要求 $1\le l\le K$ 且 $l<r\le N$，因此数量为 $\sum_{l=1}^{K}(N-l)=KN-K(K+1)/2$。当 $K=N$ 时，恒等排列自身还要额外计入一次。

复杂度

逐个测试扫描 $K$ 即可，总时间复杂度为 $O(\sum N)$，除输入数组外只需 $O(1)$ 额外空间。