中餐馆（三星版）

题目描述

人 $0$、人 $1$、$\ldots$、人 $(N-1)$ 按逆时针顺序等间距地围坐在转盘周围。餐桌上人 $i$ 面前放着菜 $p_i$。

你可以进行以下操作 $0$ 次或多次：

将转盘逆时针转动一圈的 $1/N$。旋转前在人 $i$ 面前的菜，现在位于人 $(i+1) \bmod N$ 面前。

操作全部结束后，人 $i$ 的沮丧度为 $k$，其中 $k$ 是使菜 $i$ 位于人 $(i-k) \bmod N$ 或人 $(i+k) \bmod N$ 面前的最小整数。

求 $N$ 个人的沮丧度之和的最小可能值。

什么是 $a \bmod m$？ 对于整数 $a$ 和正整数 $m$，$a \bmod m$ 表示满足 $(a-x)$ 是 $m$ 的倍数的整数 $x$（$0 \le x \le m-1$）。（可以证明这样的 $x$ 是唯一的。）

输入格式

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

$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

数据范围

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