题目描述

回転テーブルの周りに人 $0$、人 $1$、$\ldots$、人 $N-1$ がこの順番で反時計回りに等間隔で並んでいます。また、人 $i$ の目の前には料理 $p_i$ が置かれています。
あなたは次の操作を $0$ 回以上何度でも行うことが出来ます。

• 回転テーブルを反時計回りに $1$ 周の $\frac{1}{N}$ だけ回す。これによって、(この操作の直前に)人 $i$ の目の前にあった料理は人 $(i+1)\ \bmod\ N$ の目の前に移動する。

操作を完了させた後において、人 $i$ の不満度は料理 $i$ が人 $(i-k)\ \bmod\ N$、人 $(i+k)\ \bmod\ N$ のいずれかの目の前に置かれているような最小の非負整数 $k$ です。
$N$ 人の不満度の総和の最小値を求めてください。

$a\ \bmod\ m$ とは 整数 $a$ と正整数 $m$ に対し、$a\ \bmod\ m$ は $a-x$ が $m$ の倍数となるような $0$ 以上 $m$ 未満の整数 $x$ を表します。(このような $x$ は一意に定まることが証明できます)

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $p_0$ $\ldots$ $p_{N-1}$

输出格式

答えを出力せよ。

题目大意

$n$ 个人进行圆排列，即围坐在圆桌周围，位置编号依次为 $[0, n - 1]$，给定序列 $P_n$ 表示第 $i$ 个人喜欢的菜品在 $P_i$ 处，$P_i \in [0, n - 1]$ 且各不相同。定义每个人的沮丧值为其位置与 $P_i$ 的距离。你可以任意旋转圆桌，以最小化所有人的沮丧值之和，求最小值。

4
1 2 0 3

2

3
0 1 2

0

10
3 9 6 1 7 2 8 0 5 4

20

提示

制約

• $3\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $0\ \leq\ p_i\ \leq\ N-1$
• $i\ \neq\ j$ ならば $p_i\ \neq\ p_j$
• 入力はすべて整数

Sample Explanation 1

操作を $1$ 回行うと下の画像のようになります。  この時、不満度の総和が $2$ になることを以下のように確かめられます。 - 人 $0$ の不満度は、料理 $0$ が人 $3\ (=(0-1)\ \bmod\ 4)$ の目の前に置かれているので $1$ です。 - 人 $1$ の不満度は、料理 $1$ が人 $1\ (=(1+0)\ \bmod\ 4)$ の目の前に置かれているので $0$ です。 - 人 $2$ の不満度は、料理 $2$ が人 $2\ (=(2+0)\ \bmod\ 4)$ の目の前に置かれているので $0$ です。 - 人 $3$ の不満度は、料理 $3$ が人 $0\ (=(3+1)\ \bmod\ 4)$ の目の前に置かれているので $1$ です。 不満度の総和を $2$ より小さくすることは出来ないため、答えは $2$ です。