F - Replace by Average Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

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

制約

  • 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

Score : 1000 points

Problem Statement

Given is a sequence of N positive integers A = (A_1, A_2, \ldots, A_N).

You can do the following operation on this sequence any number of times.

  • Choose integers i, j, k such that 1\leq i < j < k \leq N and j = \frac{i+k}{2}. Replace A_j with \lfloor\frac{A_i+A_k}{2}\rfloor.

Find the minimum possible value of \sum_{i=1}^N A_i after the operations.

Constraints

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

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

5
2 2 5 5 4

Sample Output 1

13

The following operations achieves \sum_{i=1}^N A_i = 13.

  • Do the operation with (i,j,k) = (1,3,5). The sequence A is now (2,2,3,5,4).
  • Do the operation with (i,j,k) = (3,4,5). The sequence A is now (2,2,3,3,4).
  • Do the operation with (i,j,k) = (2,3,4). The sequence A is now (2,2,2,3,4).

Sample Input 2

5
3 1 4 1 5

Sample Output 2

11

Sample Input 3

3
3 1 3

Sample Output 3

7

Sample Input 4

3
3 5 3

Sample Output 4

9