問題文

$N$ 項からなる正整数列 $A = (A_1, A_2, \\ldots, A_N)$ が与えられます。

あなたはこの数列に対して、次の操作を何度でも行うことができます。

• $1\\leq i < j < k \\leq N$ かつ $j = \\frac{i+k}{2}$ となる整数 $i, j, k$ を選ぶ。$A_j$ を $\\lfloor\\frac{A_i+A_k}{2}\\rfloor$ に置き換える。

操作後の $\\sum_{i=1}^N A_i$ としてありうる最小値を求めてください。

制約

• $3\\leq N\\leq 3\\times 10^5$
• $1\\leq A_i\\leq 10^{12}$

入力

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

$N$ $A_1$ $A_2$ $\\ldots$ $A_N$

出力

答えを出力してください。

入力例 1

5
2 2 5 5 4

出力例 1

13

次のように操作を行うことで、$\\sum_{i=1}^N A_i = 13$ を実現できます。

• $(i,j,k) = (1,3,5)$ として操作を行う。数列 $A$ は $(2,2,3,5,4)$ へと変化する。
• $(i,j,k) = (3,4,5)$ として操作を行う。数列 $A$ は $(2,2,3,3,4)$ へと変化する。
• $(i,j,k) = (2,3,4)$ として操作を行う。数列 $A$ は $(2,2,2,3,4)$ へと変化する。

入力例 2

5
3 1 4 1 5

出力例 2

11

入力例 3

3
3 1 3

出力例 3

7

入力例 4

3
3 5 3

出力例 4

9