糖果分装

题目背景

幼儿园的 $n$ 个小朋友排成一排坐在长桌前，每人面前放着一个盒子，盒子里装着若干颗糖。保育员希望每个盒子里的糖果数量都一样多，可是她只能让小朋友把糖果递给相邻的伙伴。

题目描述

$n$ 个盒子从左到右排成一排，第 $i$ 个盒子里有 $a_i$ 颗糖。

保育员的一次操作是这样的：选择两个相邻的盒子，把其中一个盒子里的任意多颗糖（可以是 $0$ 颗）搬到另一个盒子里。一次操作的代价等于被搬动的糖果颗数。

保育员希望通过若干次操作，使每个盒子里的糖果数量都相同。请你求出所需的最小总代价；如果无论如何都无法做到，输出 $-1$。

糖果只能在相邻盒子之间传递，中途不能被临时放在别的地方。同一个盒子可以参与多次操作。

输入格式

从标准输入读入数据。

第一行一个整数 $n$，表示盒子的个数。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，依次表示每个盒子里初始的糖果数量。

输出格式

输出到标准输出。

一行一个整数，表示最小总代价；若无法做到，输出 $-1$。

样例 1 输入

3
1 2 3

样例 1 输出

2

样例 1 解释

目标状态是每盒 $2$ 颗。把第 $1$ 盒的 $1$ 颗糖搬到第 $2$ 盒，代价为 $1$；再把第 $3$ 盒的 $1$ 颗糖搬到第 $2$ 盒，代价为 $1$。总代价为 $2$，并且无法更小。

样例 2 输入

4
5 0 0 3

样例 2 输出

5

样例 2 解释

目标状态是每盒 $2$ 颗。一种最优方案是：第 $1$ 盒先搬 $2$ 颗到第 $2$ 盒（代价 $2$），第 $3$ 盒没有糖，第 $1$ 盒再搬 $1$ 颗给第 $2$ 盒、第 $2$ 盒搬 $1$ 颗给第 $3$ 盒（代价 $2$），最后第 $4$ 盒搬 $1$ 颗到第 $3$ 盒（代价 $1$），总代价为 $5$。

样例 3 输入

3
1 2 4

样例 3 输出

-1

样例 3 解释

糖果总数是 $7$，不能被 $3$ 个盒子平分，因此无法让每个盒子里的糖果数量都相同。

数据范围

特殊性质 A：所有 $a_i$ 都相等。

特殊性质 B：保证 $\sum_{i=1}^{n} a_i$ 是 $n$ 的倍数。

提交说明

本题使用标准输入输出。程序应从标准输入读入数据，并将答案输出到标准输出。