Iron Bar Cutting

题意翻译

高桥君想把 $n$ 个铁棒分成两组,使得它们的长度之和相等。 但是有时可能不能分成两组,于是他考虑了两种操作。每次操作要花费他一块钱。 1. 他可以将任意铁棒增长 $1$ 毫米。 1. 他可以将长度大于 $1$ 毫米的铁棒缩短 $1$ 毫米。 因为高桥君很穷,所以请求出他至少要用多少块钱才能完成这个任务。

题目描述

[problemUrl]: https://ddcc2020-qual.contest.atcoder.jp/tasks/ddcc2020_qual_b DISCO 社の高橋君の前に, $ 1 $ 本の鉄の棒が置かれています. この棒は, $ N-1 $ 個の切れ目によって $ N $ 個の区間に分かれています.左から $ i $ 個目の区間の長さは $ A_i $ ミリメートルです. 高橋君は,切れ目を一つ選んでそこで棒を切り,同じ長さの棒を $ 2 $ 本作ることを考えました.しかし,今の状態では,どの切れ目を選んでも $ 2 $ 本の棒を同じ長さにすることができないかもしれません. そこで,彼は棒を切る**前に**,以下の操作を何回か行うことにしました. - 棒の区間のうち $ 1 $ つを選び,膨張させ,長さを $ 1 $ ミリメートル増やす.この操作を $ 1 $ 回行うのに $ 1 $ 円かかる. - 棒の区間のうち長さが $ 2 $ ミリメートル以上のもの $ 1 $ つを選び,収縮させ,長さを $ 1 $ ミリメートル減らす.この操作を $ 1 $ 回行うのに $ 1 $ 円かかる. 彼が棒を $ 2 $ 等分するために必要な最小の金額は何円か,求めてください. Takahashi, who works at DISCO, is standing before an iron bar. The bar has $ N-1 $ notches, which divide the bar into $ N $ sections. The $ i $ -th section from the left has a length of $ A_i $ millimeters. Takahashi wanted to choose a notch and cut the bar at that point into two parts with the same length. However, this may not be possible as is, so he will do the following operations some number of times **before** he does the cut: - Choose one section and expand it, increasing its length by $ 1 $ millimeter. Doing this operation once costs $ 1 $ yen (the currency of Japan). - Choose one section of length at least $ 2 $ millimeters and shrink it, decreasing its length by $ 1 $ millimeter. Doing this operation once costs $ 1 $ yen. Find the minimum amount of money needed before cutting the bar into two parts with the same length.

输入输出格式

输入格式


Input is given from Standard Input in the following format: ``` $ N $ $ A_1 $ $ A_2 $ $ A_3 $ $ ... $ $ A_N $ ```

输出格式


Print an integer representing the minimum amount of money needed before cutting the bar into two parts with the same length.

输入输出样例

输入样例 #1

3
2 4 3

输出样例 #1

3

输入样例 #2

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

输出样例 #2

输入样例 #3

3
2 4 3

输出样例 #3

3

输入样例 #4

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

输出样例 #4

说明

### 制約 - $ 2\ \leq\ N\ \leq\ 200000 $ - $ 1\ \leq\ A_i\ \leq\ 2020202020 $ - $ N,\ A_i $ は整数 ### Constraints - $ 2\ \leq\ N\ \leq\ 200000 $ - $ 1\ \leq\ A_i\ \leq\ 2020202020 $ - All values in input are integers. ### Sample Explanation 1 最初,棒の各区間の長さは $ [2,\ 4,\ 3] $ (ミリメートル) です.高橋君は,以下の操作を行うことによって, $ 3 $ 円で棒を $ 2 $ 等分できます. - 左から $ 2 $ 番目の区間を収縮させる.各区間の長さは $ [2,\ 3,\ 3] $ となる. - 左から $ 1 $ 番目の区間を収縮させる.各区間の長さは $ [1,\ 3,\ 3] $ となる. - 左から $ 2 $ 番目の区間を収縮させる.各区間の長さは $ [1,\ 2,\ 3] $ となる.左から $ 2 $ 個目の切れ目で棒を切ると,長さ $ 3 $ の棒が $ 2 $ 本できる. ### Sample Explanation 3 The initial lengths of the sections are $ [2,\ 4,\ 3] $ (in millimeters). Takahashi can cut the bar equally after doing the following operations for $ 3 $ yen: - Shrink the second section from the left. The lengths of the sections are now $ [2,\ 3,\ 3] $ . - Shrink the first section from the left. The lengths of the sections are now $ [1,\ 3,\ 3] $ . - Shrink the second section from the left. The lengths of the sections are now $ [1,\ 2,\ 3] $ , and we can cut the bar at the second notch from the left into two parts of length $ 3 $ each.