在学习了 Garsia–Wachs 算法后，你提出了以下问题。

有 $n$ 堆石子排成一行。第 $i$ 堆包含 $a_i$ 个石子。你想要将所有石子合并成一堆。

首先，你将选择第 $k$ 堆。然后，你可以对选定的石子堆执行以下操作：选择选定堆的左侧或右侧相邻堆，并将它们合并成一堆。操作后，新合并的堆成为选定堆。在执行此操作 $n - 1$ 次后，将只剩下一堆石子。每次合并操作的代价是新堆中石子的数量。

你需要求出如果初始选择第 $k$ 堆时，合并所有石子的最小总代价。对于 $k = 1, 2, \dots, n$，输出对应的答案。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$)。

输出格式

输出 $n$ 个整数。第 $k$ 个数字表示初始选择第 $k$ 堆时的最小总代价。

样例

样例输入 1

5
2 1 3 5 4

样例输出 1

35 35 36 43 49

样例输入 2

10
18 37 81 6 58 99 87 34 75 9

样例输出 2

2637 2637 2657 2657 2695 2949 2995 2905 2880 2880

说明

如果你初始选择第 4 堆，过程可以如下进行： $\{2, 1, 3, 5, 4\} \to \{2, 1, 8, 4\} \to \{2, 9, 4\} \to \{11, 4\} \to \{15\}$。 总代价为 $8 + 9 + 11 + 15 = 43$。