题目描述

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

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

选定满足 $1\le i,j\le n$ 的下标 $i$ 和 $j$，将 $a_i$ 赋值为 $a_i+1$，同时将 $a_j$ 赋值为 $a_j-1$。$i$ 和 $j$ 不能相同。

求使得前缀和之和等于后缀和之和的最小操作次数。

也就是说，令 $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$。

注意，$a_i$ 可以变为负数。

输入格式

第一行一个整数 $n$。

第二行用空格隔开的 $n$ 个整数，表示 $a$ 序列。

输出格式

输出一行一个整数表示最小操作次数。

若无解，输出 $-1$。

5
1 2 3 4 5

3

6
2 3 7 4 5 8

-1

提示

本题采用捆绑测试。

• Subtask 1（30 pts）：$1 \le n \le 2$；
• Subtask 2（30 pts）：$a_i=i$；
• Subtask 3（5 pts）：$a_i=1$；
• Subtask 4（35 pts）：无特殊限制。

对于所有数据，保证 $1 \le n,a_i \le 10^6$。