分数: 1000 点
问题陈述
给定的是一系列 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.
找到以下的最小可能值 \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