题解
题目中要求, 位置 \(i\) 上的数要运动到位置 \(u_i = (p_i+k)\bmod n\), 其中 \(k\) 可以任选. 假设位置 \(i\) 上的数运动过程中, 它总共以逆时针方向运动了 \(x_i\) 个单位 (可为负数). 把全部的 \(x_i\) 均加上一个常数，仍然会是合法的.
通过调整法可证:
- 不可能出现, 逆时针方向下，\(i\) 超过了 \(j\) \(2\) 次的情况;
- (严格强于上一个条件) \(|x_i-x_j|<n\).
可设 \(0\le x_i<n\). 假设 \(i\) 逆时针走到 \(p_i\) 的弧为 \(\alpha_i\).
可以进行的操作有:
- 交换 \(\alpha_i, \alpha_{i+1}\) 的终点 (代价为 \(1\));
- 给所有 \(x_i\) 加上任意常数 (代价为 \(0\)).
(所有加法运算均在\(\bmod n\) 意义下进行.)
如果忽略操作 \(2\), 只需使 \(\forall i\ne j, \alpha_i \not \subset \alpha_j\). 而且，若存在这样的包含关系，必能用 \(1\) 次操作 \(1\) 去除恰好 \(1\) 对包含关系。
只需算出 \(\sum_{i\ne j} \alpha_i\subset \alpha_j\) 的最大值 \(mx\), 它是答案的上界. 发现, 相交关系可以均调整为包含关系. 包含关系有着内向树的结构，而任意子树大小不超过 \(\lceil n/2 \rceil\). 故:
\[\begin{split}
mx &= \binom{\lfloor n/2\rfloor}{2} + \binom{\lceil n/2 \rceil}{2} \\
&= 2401
\end{split}
\]