题目描述

给定一个长度为 $n$ 的整数序列 $a$。

您可以对这个序列进行若干次（可以为 $0$ 次）操作，每次操作规则如下：

• 选定满足 $1 \le i, j \le n$ 的下标 $i$ 和 $j$（且 $i \neq j$），将 $a_i$ 赋值为 $a_i+1$，同时将 $a_j$ 赋值为 $a_j-1$。

注意，操作过程中 $a_i$ 可以变为负数。

请计算出使得前缀和之和等于后缀和之和的最小操作次数。

也就是说，令 $s_i = a_1 + a_2 + \dots + a_i$，$t_i = a_i + a_{i+1} + \dots + a_n$，你需要通过最少的操作次数，使得最终序列满足 $s_1 + s_2 + \dots + s_n = t_1 + t_2 + \dots + t_n$。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，相邻两个整数之间用一个空格隔开，表示初始序列 $a$。

输出格式

输出一行，一个整数，表示最少需要的操作次数。如果无论如何操作都无法满足条件，输出 -1。

样例输入 1

5
1 2 3 4 5

样例输出 1

3

样例输入 2

6
2 3 7 4 5 8

样例输出 2

-1

说明

数据范围

对于所有测试点，保证:

• $1 \le n \le 10^6$ ,
• $1 \le a_i \le 10^6$ ,
• 保证所有的输入数值均为整数。