题目描述

$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$ としてありうる最小値を求めてください。

输入格式

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

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

输出格式

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

题目大意

给定一个数组，可以进行以下操作任意多次。

选定 $1\leq i<j<k\leq N$ ，将 $a_j$ 改为 $\lfloor\frac{A_i+A_k}{2}\rfloor$ 。

求数组所有数的和的最小值。

5
2 2 5 5 4

13

5
3 1 4 1 5

11

3
3 1 3

7

3
3 5 3

9

提示

制約

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

Sample Explanation 1

次のように操作を行うことで、$\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)$ へと変化する。