A - Watering the Flower Bed Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君は N 個の花壇を管理しています。

i 番目の花壇には、現在 A_i リットルの水が入っています。高橋君は、すべての花壇の水の量を等しくしたいと考えています。

高橋君は以下の操作を好きな回数（ 0 回でもよい）行うことができます。

  • 花壇を 1 つ選び、その花壇に水を 1 リットル追加する。この操作には 1 円かかる。同じ花壇を何度選んでもよい。

花壇から水を抜くことはできないため、操作後の各花壇の水の量は操作前以上になります。

高橋君は、すべての花壇の水の量がある整数値で等しくなることを目標とします。目標とする値は自由に決めることができます。

この目標を達成するために必要な最小の費用（円）を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、花壇の数を表す整数 N が与えられる。
  • 2 行目には、各花壇に入っている水の量を表す N 個の整数 A_1, A_2, \ldots, A_N が空白区切りで与えられる。

出力

すべての花壇の水の量を等しくするために必要な最小の費用（円）を 1 行で出力せよ。

入力例 1

3
2 5 3

出力例 1

5

入力例 2

5
10 10 10 10 10

出力例 2

0

入力例 3

6
1 100 50 25 75 200

出力例 3

749

Score : 233 pts

Problem Statement

Takahashi manages N flower beds.

The i-th flower bed currently contains A_i liters of water. Takahashi wants to make the amount of water in all flower beds equal.

Takahashi can perform the following operation any number of times (possibly 0 times):

  • Choose one flower bed and add 1 liter of water to it. This operation costs 1 yen. The same flower bed may be chosen multiple times.

Since water cannot be removed from a flower bed, the amount of water in each flower bed after the operations will be at least the amount before the operations.

Takahashi's goal is to make the amount of water in all flower beds equal to some integer value. He is free to choose the target value.

Find the minimum cost (in yen) required to achieve this goal.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • All inputs are integers

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N, representing the number of flower beds.
  • The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the amount of water in each flower bed.

Output

Print in one line the minimum cost (in yen) required to make the amount of water in all flower beds equal.

Sample Input 1

3
2 5 3

Sample Output 1

5

Sample Input 2

5
10 10 10 10 10

Sample Output 2

0

Sample Input 3

6
1 100 50 25 75 200

Sample Output 3

749