分数: 500 点
问题陈述
人 0, 人 1, \ldots和人 (N-1) 按逆时针顺序坐在转盘周围,间隔均匀。 菜品 p_i 在人的前面 i 在桌子上。
您可以执行以下操作 0 或多次:
- 将转盘旋转一圈 N- 逆时针旋转一圈。 人面前的菜 i 旋转之前现在位于 Person 的前面 (i+1) \bmod N.
当你完成后,Person i 获得挫败感 k,其中 k 是满足 Dish 的最小整数 i 位于任一人的前面 (i-k) \bmod N 或人 (i+k) \bmod N.
求最小可能的挫败感总和 N 人。
什么是 a \bmod m?
对于整数 a 和一个正整数 m, a \bmod m 表示整数 x 之间 0 和 (m-1) (含)使得 (a-x) 是的倍数 m。 (可以证明这样 x 是唯一的。)约束
- 3 \leq N \leq 2 \times 10^5
- 0 \leq p_i \leq N-1
- p_i \neq p_j if i \neq j.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
p_0 \ldots p_{N-1}
输出
打印答案。
示例输入 1
4 1 2 0 3
示例输出 1
2
下图为一次操作后的表格。

在这里,他们的挫败感是 2 因为:
- 人 0 感到沮丧 1 自从菜 0 在人的前面 3\ (=(0-1) \bmod 4);
- 人 1 感到沮丧 0 自从菜 1 在人的前面 1\ (=(1+0) \bmod 4);
- 人 2 感到沮丧 0 自从菜 2 在人的前面 2\ (=(2+0) \bmod 4);
- 人 3 感到沮丧 1 自从菜 3 在人的前面 0\ (=(3+1) \bmod 4).
我们不能让他们的挫败感总和小于 2,所以答案是 2.
示例输入 2
3 0 1 2
示例输出 2
0
示例输入 3
10 3 9 6 1 7 2 8 0 5 4
示例输出 3
20