分数: 200 点
问题陈述
在 DISCO 工作的高桥正站在一根铁棍前。 酒吧有 N-1 凹口,将条分为 N 部分。 i从左边算起第一个部分的长度为 A_i 毫米。
高桥想要选择一个凹口,并将该点处的条切成长度相同的两部分。 然而,这可能不可能,所以他会多次执行以下操作 之前 他进行了剪辑:
- 选择一个部分并将其展开,将其长度增加 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 日元:
- 缩小左侧第二个部分。现在各部分的长度是 [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