配点 : $1000$ 点

問題文

$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$

出力

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

5
2 2 5 5 4

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)$ へと変化する。

5
3 1 4 1 5

11

3
3 1 3

7

3
3 5 3

9