当前没有测试数据。

E - 中餐厅（3星版本）

分数：500分

问题描述

0号人，1号人，... ，以及(N-1)号人坐在圆桌周围，等距离分布。第i道菜在第i号人的面前。
您可以进行以下操作0次或多次：

• 将圆盘逆时针旋转$N$分之$1$圈。旋转之前在第i号人面前的菜放在第$(i+1) \bmod N$号人的面前。

最后，第i号人的不满为$k$，其中$k$是满足第i道菜在第$(i-k) \bmod N$或第$(i+k) \bmod N$号人面前的最小整数。
找出$N$个人的最小可能不满之和。

约束

• $3 \leq N \leq 2 \times 10^5$
• $0 \leq p_i \leq N-1$
• 当$i \neq j$时，$p_i \neq p_j$。
• 所有输入值均为整数。

输入

从标准输入中按以下格式给出：

$N$

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

输出

输出答案。

4
1 2 0 3

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。

3
0 1 2

0

10
3 9 6 1 7 2 8 0 5 4

20