AT_abc268_e [ABC268E] Chinese Restaurant (Three-Star Version)

在转盘桌的周围，按照逆时针方向等间隔地排列着人 $0$、人 $1$、$\ldots$、人 $N-1$。此外，在人 $i$ 的正前方放着菜品 $p_i$。 你可以进行如下操作任意多次（包括 $0$ 次）： - 将转盘桌逆时针旋转 $\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$ $p_1$ $\ldots$ $p_{N-1}$

请输出答案。

### 限制条件 - $3 \leq N \leq 2 \times 10^5$ - $0 \leq p_i \leq N-1$ - 若 $i \neq j$，则 $p_i \neq p_j$ - 输入均为整数 ### 样例解释 1 若进行 $1$ 次操作，情况如下图所示。  此时，不满度总和为 $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$。 由 ChatGPT 4.1 翻译