E - Chinese Restaurant (Three-Star Version) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500

問題文

回転テーブルの周りに人 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 ma-xm の倍数となるような 0 以上 m 未満の整数 x を表します。(このような x は一意に定まることが証明できます)

制約

  • 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}

出力

答えを出力せよ。


入力例 1

4
1 2 0 3

出力例 1

2

操作を 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 です。


入力例 2

3
0 1 2

出力例 2

0

入力例 3

10
3 9 6 1 7 2 8 0 5 4

出力例 3

20

Score : 500 points

Problem Statement

Person 0, Person 1, \ldots, and Person (N-1) are sitting around a turntable in counterclockwise order, evenly spaced. Dish p_i is in front of Person i on the table.
You may perform the following operation 0 or more times:

  • Rotate the turntable by one N-th of a counterclockwise turn. The dish that was in front of Person i right before the rotation is now in front of Person (i+1) \bmod N.

When you are finished, Person i gains frustration of k, where k is the minimum integer such that Dish i is in front of either Person (i-k) \bmod N or Person (i+k) \bmod N.
Find the minimum possible sum of frustration of the N people.

What is a \bmod m? For an integer a and a positive integer m, a \bmod m denotes the integer x between 0 and (m-1) (inclusive) such that (a-x) is a multiple of m. (It can be proved that such x is unique.)

Constraints

  • 3 \leq N \leq 2 \times 10^5
  • 0 \leq p_i \leq N-1
  • p_i \neq p_j if i \neq j.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
p_0 \ldots p_{N-1}

Output

Print the answer.


Sample Input 1

4
1 2 0 3

Sample Output 1

2

The figure below shows the table after one operation.

Here, the sum of their frustration is 2 because:

  • Person 0 gains a frustration of 1 since Dish 0 is in front of Person 3\ (=(0-1) \bmod 4);
  • Person 1 gains a frustration of 0 since Dish 1 is in front of Person 1\ (=(1+0) \bmod 4);
  • Person 2 gains a frustration of 0 since Dish 2 is in front of Person 2\ (=(2+0) \bmod 4);
  • Person 3 gains a frustration of 1 since Dish 3 is in front of Person 0\ (=(3+1) \bmod 4).

We cannot make the sum of their frustration less than 2, so the answer is 2.


Sample Input 2

3
0 1 2

Sample Output 2

0

Sample Input 3

10
3 9 6 1 7 2 8 0 5 4

Sample Output 3

20