题目描述

给定一个由 $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$ 替换为 $\left\lfloor \frac{A_i + A_k}{2} \right\rfloor$。

请你求出经过若干次操作后，$\sum_{i=1}^N A_i$ 可能取得的最小值。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

请输出答案。

样例 1

输入

5
2 2 5 5 4

输出

13

样例 2

输入

5
3 1 4 1 5

输出

11

样例 3

输入

3
3 1 3

输出

7

样例 4

输入

3
3 5 3

输出

9

说明/提示

限制条件

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

样例解释 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)$。

由 ChatGPT 4.1 翻译