问题描述

给定一个包含 $N$ 个正整数的序列 $A = (A_1, A_2, \ldots, A_N)$。

你可以对该序列执行以下操作任意次：

• 选择整数 $i, j, k$，满足 $1\leq i < j < k \leq N$ 且 $j = \frac{i+k}{2}$。将 $A_j$ 替换为 $\\lfloor\\frac{A_i+A_k}{2}\\rfloor$。

找到操作后序列 $A$ 的所有元素之和的最小值。

约束条件

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