Heavy Stones

After learning the Garsia-Wachs algorithm, you came up with the following problem.

There are $n$ piles of stones in a line. The $i$-th pile contains $a_i$ stones. You want to merge all the stones into one pile.

At first, you select the $k$-th pile. Then you perform the following operation on the selected pile: choose the left or right adjacent pile of the selected one, and merge them into one pile. The new pile becomes the selected pile after the operation. After performing this operation $n-1$ times, only one pile is left. The cost of each merge operation is the number of stones in the new pile.

You want to know the smallest total cost if you select the $k$-th pile initially. For $k=1, 2, \ldots, n$, output the answer.

The first line contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^6$).

Output $n$ integers. The $k$-th number is the smallest total cost if you select the $k$-th pile initially.

If you select the 4th pile initially, the process can go as follows:

{2, 1, 3, 5, 4} → {2, 1, 8, 4} → {2, 9, 4} → {11, 4} → {15}

The total cost is 8 + 9 + 11 + 15 = 43.