在一个大型企业中，老板决定根据员工的绩效来分配奖金。给定一个长度为 n 的员工绩效列表 a_1, a_2, \ldots, a_n，表示每个员工为公司带来的绩效值。老板希望将这些员工划分成 k 段连续且非空的工作组（**每个工作组的员工至少有一名**）。

对于每个工作组 1 \leq k \leq n，我们定义每个工作组的奖金是该组所有员工绩效值的总和乘以该组的编号，即 

s_i = \sum_{j=r_{i-1}+1}^{r_i} a_j，

其中 1 \leq i \leq k，r_0 = 0 且 r_k = n，并且 r_1, r_2, \ldots, r_{k-1} 依次为各个组的分割点，满足 r_0 < r_1 < r_2 < \ldots < r_{k-1} < r_k。

老板的目标是，在划分员工组时，使以下公式的值最大化：

\sum_{i=1}^{k} i \times s_i

换句话说，老板希望在分配奖金时，不仅考虑每个工作组的绩效值之和，还希望根据工作组的顺序来奖励更高顺位的团队。

对于每个 1 \leq k \leq n，找出最大化上述公式的方案，并输出该最大值。

第一行输入一个整数 n (1 \leq n \leq 5 \times 10^5)，表示员工的数量。  

第二行输入 n 个整数 a_1, a_2, \ldots, a_n（-10^6 \leq a_i \leq 10^6），表示每个员工的绩效值。

输出 n 个整数，第 i 个整数表示当员工被划分成 i 个工作组时，能获得的最大奖金总和。

解释

考虑 k = 3，将员工划分为 \{1\} \{3, -4\}, \{5, -1, -2\} 答案为 1 \times 1 + 2 \times (3 - 4) + 3 \times (5 - 1 - 2) = 5\

数据范围与约定

- 对于 20\% 的数据，满足 n \leq 10

- 对于 40\% 的数据，满足 n \leq 2000

- 对于 100\% 的数据，满足 1 \leq n \leq 5 \times 10^5, -10^6 \leq a_i \leq 10^6