题目描述

DISCO 社の高橋君の前に，$1$ 本の鉄の棒が置かれています．
この棒は，$N-1$ 個の切れ目によって $N$ 個の区間に分かれています．左から $i$ 個目の区間の長さは $A_i$ ミリメートルです．

高橋君は，切れ目を一つ選んでそこで棒を切り，同じ長さの棒を $2$ 本作ることを考えました．しかし，今の状態では，どの切れ目を選んでも $2$ 本の棒を同じ長さにすることができないかもしれません．
そこで，彼は棒を切る前に，以下の操作を何回か行うことにしました．

• 棒の区間のうち $1$ つを選び，膨張させ，長さを $1$ ミリメートル増やす．この操作を $1$ 回行うのに $1$ 円かかる．
• 棒の区間のうち長さが $2$ ミリメートル以上のもの $1$ つを選び，収縮させ，長さを $1$ ミリメートル減らす．この操作を $1$ 回行うのに $1$ 円かかる．

彼が棒を $2$ 等分するために必要な最小の金額は何円か，求めてください．

输入格式

入力は以下の形式で標準入力から与えられます．

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

输出格式

高橋君が棒を $2$ 等分するのにかかる最小の金額を整数で出力してください．

题目大意

高桥君想把 $n$ 个铁棒分成两组，使得它们的长度之和相等。

但是有时可能不能分成两组，于是他考虑了两种操作。每次操作要花费他一块钱。

1. 他可以将任意铁棒增长 $1$ 毫米。
2. 他可以将长度大于 $1$ 毫米的铁棒缩短 $1$ 毫米。

因为高桥君很穷，所以请求出他至少要用多少块钱才能完成这个任务。

3
2 4 3

3

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

0

提示

制約

• $2\ \leq\ N\ \leq\ 200000$
• $1\ \leq\ A_i\ \leq\ 2020202020$
• $N,\ A_i$ は整数

Sample Explanation 1

最初，棒の各区間の長さは $[2,\ 4,\ 3]$ (ミリメートル) です．高橋君は，以下の操作を行うことによって，$3$ 円で棒を $2$ 等分できます． - 左から $2$ 番目の区間を収縮させる．各区間の長さは $[2,\ 3,\ 3]$ となる． - 左から $1$ 番目の区間を収縮させる．各区間の長さは $[1,\ 3,\ 3]$ となる． - 左から $2$ 番目の区間を収縮させる．各区間の長さは $[1,\ 2,\ 3]$ となる．左から $2$ 個目の切れ目で棒を切ると，長さ $3$ の棒が $2$ 本できる．