← 返回题目列表

AtCoder · awc0100_d

D. 团队划分

中文机器翻译题面 查看原题

分数: 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