题目描述

Takahashi 在 DISCO 公司工作，他站在一根铁棒前面。这根铁棒上有 $N-1$ 个凹槽，将铁棒分成了 $N$ 段。从左边数第 $i$ 段的长度为 $A_i$ 毫米。

Takahashi 希望选择一个凹槽，在那里将铁棒切割成两段完全相同的长度。然而，由于初始条件可能不满足他的要求，所以他会在切割之前进行以下操作：

• 选择一段铁棒，并使其长度增加 $1$ 毫米。这个操作花费 $1$ 日元（日本的货币）。
• 选择一段长度至少为 $2$ 毫米的铁棒，并使其长度减少 $1$ 毫米。这个操作花费 $1$ 日元。

求在将铁棒切割成两段相同长度之前，所需要的最小花费金额。

约束条件

• $2 \\leq N \\leq 200000$
• $1 \\leq A_i \\leq 2020202020$
• 输入的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $A_1$ $A_2$ $A_3$ $...$ $A_N$

输出

按整数形式输出，在将铁棒切割成两段相同长度之前所需的最小花费金额。

输入样例 1

3
2 4 3

输出样例 1

3

初始时，各段铁棒的长度分别为 \[2, 4, 3\]（单位：毫米）。在进行以下 3 步操作后，Takahashi 可以将铁棒等分，花费了 3 日元：

• 缩短左边第二段铁棒的长度。此时，三段铁棒的长度变为 \[2, 3, 3\]。
• 缩短左边第一段铁棒的长度。此时，三段铁棒的长度变为 \[1, 3, 3\]。
• 缩短左边第二段铁棒的长度。此时，三段铁棒的长度变为 \[1, 2, 3\]，然后我们可以在从左边数第二个凹槽处将铁棒切割成两段长度均为 $3$ 的部分。

输入样例 2

12
100 104 102 105 103 103 101 105 104 102 104 101

输出样例 2

0