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 m は a-x が m の倍数となるような 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