配点: $200$ 点

問題文

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

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

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

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

制約

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

入力

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

$N$

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

出力

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

3
2 4 3

3

最初，棒の各区間の長さは $[2, 4, 3]$ (ミリメートル) です．高橋君は，以下の操作を行うことによって，$3$ 円で棒を $2$ 等分できます．

• 左から $2$ 番目の区間を収縮させる．各区間の長さは $[2, 3, 3]$ となる．
• 左から $1$ 番目の区間を収縮させる．各区間の長さは $[1, 3, 3]$ となる．
• 左から $2$ 番目の区間を収縮させる．各区間の長さは $[1, 2, 3]$ となる．左から $2$ 個目の切れ目で棒を切ると，長さ $3$ の棒が $2$ 本できる．

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

0