D - Equal Distribution of Cake Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は、N 人の子どもたちにケーキを配る係を任されました。子どもたちは左から順に子ども 1, 子ども 2, ..., 子ども N と番号が付けられており、一列に並んでいます。

現在、子ども i は A_i 個のケーキを持っています。高橋君は、すべての子どもが同じ数のケーキを持つように調整したいと考えています。

高橋君は以下の操作を何度でも行うことができます：

  • 隣り合う2人の子ども（子ども j と子ども j+1、ただし 1 \leq j \leq N-1）を選び、どちらか一方から他方へケーキを 1 個移動させる。ただし、ケーキを 0 個しか持っていない子どもからケーキを移動させることはできない。

ケーキの総数は操作を通じて変わりません。新たにケーキを追加したり、ケーキを捨てたりすることはできません。

すべての子どもが持っているケーキの数を等しくするために必要な操作の最小回数を求めてください。ただし、ケーキの総数が N で割り切れず、目標を達成することが不可能な場合は -1 を出力してください。

制約

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

入力

N
A_1 A_2 \cdots A_N
  • 1 行目には、子どもの人数を表す整数 N が与えられる。
  • 2 行目には、各子どもが持っているケーキの個数を表す N 個の整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

すべての子どものケーキの個数を等しくするために必要な最小操作回数を 1 行で出力してください。目標を達成することが不可能な場合は -1 を出力してください。

入力例 1

3
1 2 3

出力例 1

2

入力例 2

3
1 2 4

出力例 2

-1

入力例 3

5
0 0 0 0 10

出力例 3

20

Score : 400 pts

Problem Statement

Takahashi has been assigned the task of distributing cakes to N children. The children are numbered child 1, child 2, ..., child N from left to right, and they are standing in a single line.

Currently, child i has A_i cakes. Takahashi wants to adjust the cakes so that all children have the same number of cakes.

Takahashi can perform the following operation any number of times:

  • Choose two adjacent children (child j and child j+1, where 1 \leq j \leq N-1), and move 1 cake from one of them to the other. However, it is not possible to move a cake from a child who has 0 cakes.

The total number of cakes does not change through operations. It is not possible to add new cakes or discard cakes.

Find the minimum number of operations required to make the number of cakes held by all children equal. If the total number of cakes is not divisible by N and it is impossible to achieve the goal, output -1.

Constraints

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

Input

N
A_1 A_2 \cdots A_N
  • The first line contains an integer N representing the number of children.
  • The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the number of cakes each child has.

Output

Output in one line the minimum number of operations required to make the number of cakes equal for all children. If it is impossible to achieve the goal, output -1.

Sample Input 1

3
1 2 3

Sample Output 1

2

Sample Input 2

3
1 2 4

Sample Output 2

-1

Sample Input 3

5
0 0 0 0 10

Sample Output 3

20