题目描述
Problem Description
In front of Takahashi from DISCO Corporation, there is a single iron bar.
This bar is divided into $ N $ sections by $ N-1 $ cut marks. The length of the $ i $-th section from the left is $ A_i $ millimeters.
Takahashi thought about choosing one of the cut marks and cutting the bar there to make two bars of the same length. However, it might not be possible to make two bars of the same length with any cut mark in its current state.
Therefore, he decided to perform the following operations before cutting the bar.
- Choose one of the sections of the bar and expand it, increasing its length by $ 1 $ millimeter. This operation costs $ 1 $ yen.
- Choose one of the sections of the bar with a length of $ 2 $ millimeters or more and shrink it, decreasing its length by $ 1 $ millimeter. This operation also costs $ 1 $ yen.
Find the minimum amount of money required for him to cut the bar into two equal parts.
Input Format
The input is given from the standard input in the following format.
$ N $ $ A_1 $ $ A_2 $ $ A_3 $ ... $ A_N $
Output Format
Output the minimum amount of money Takahashi needs to cut the bar into two equal parts as an integer.
Sample Input and Output
Sample Input #1
3
2 4 3
Sample Output #1
3
Sample Input #2
12
100 104 102 105 103 103 101 105 104 102 104 101
Sample Output #2
0
Notes/Hints
Constraints
- $2 \leq N \leq 200000$
- $1 \leq A_i \leq 2020202020$
- $ N, A_i $ are integers
Sample Explanation 1
Initially, the lengths of the sections of the bar are $ [2, 4, 3] $ millimeters. Takahashi can cut the bar into two equal parts for $ 3 $ yen by performing the following operations:
- Shrink the second section from the left. The lengths of the sections become $ [2, 3, 3] $.
- Shrink the first section from the left. The lengths of the sections become $ [1, 3, 3] $.
- Shrink the second section from the left again. The lengths of the sections become $ [1, 2, 3] $. Cutting the bar at the second cut mark from the left results in two bars of length $ 3 $.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分