均分搬运

题目描述

n堆物品的数量都是非负整数。每次从一堆搬一个到另一堆，允许任意两堆之间搬运。求使各堆一样多的最少搬运次数；不能均分时输出-1。

输入格式

第一行输入n，第二行输入n个整数，按原顺序排列。

输出格式

输出最少次数或-1。

样例 1

输入

3
0 6 3

输出

3

说明

从第二堆搬3个到第一堆。

样例 2

输入

2
1 2

输出

-1

说明

总数3不能均分给2堆。

数据范围

• 1 ≤ n ≤ 200
• 每个元素为0至1000之间的整数；允许重复。