← 返回题目列表

AtCoder · arc130_f

F. 替换为平均值

中文机器翻译题面 查看原题

分数: 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