分数: 300 分
问题陈述
高桥是一个由以下人员组成的团体的领导者 N 成员。成员编号为 1 to N,以及成员的技能值 i (1 \le i \le N) is A_i.
高桥想以连续号码的边界将这个小组分成两队。具体来说,他选择一个整数 k (1 \le k < N),并分配成员 1 通过 k 致“A队”和成员们 k+1 通过 N 到“B 队”。
设 A 队的技能值总和为 S_1 = A_1 + A_2 + \cdots + A_k,B队的技能值之和为 S_2 = A_{k+1} + A_{k+2} + \cdots + A_N.
找到最小值 |S_1 - S_2| 当 k 被最佳选择。
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 所有输入均为整数
输入
N A_1 A_2 \cdots A_N
- 第一行包含一个整数 N 代表会员数量。
- 第二行包含 N 整数 A_1, A_2, \ldots, A_N 以空格分隔,代表成员的技能值 1 通过 N.
输出
打印最小值 |S_1 - S_2| 在一行上。
示例输入 1
4 1 2 3 4
示例输出 1
2
示例输入 2
5 1 3 2 2 4
示例输出 2
0
示例输入 3
15 8 1 6 3 5 7 4 9 2 10 12 11 14 13 15
示例输出 3
10
示例输入 4
40 17 23 5 11 29 31 7 13 19 2 37 41 3 43 47 53 59 61 67 71 73 79 83 89 97 101 107 109 113 127 131 137 139 149 151 157 163 167 173 179
示例输出 4
71
示例输入 5
2 1000000000 1000000000
示例输出 5
0