给你1个长度为n的数字序列，请你将数字序列分割成k段，每段中的最大值为Zi,请你计算下，当k=1....n时，每段的zi相加后的值最小是多少?，数字序列长度为1≤n≤8000,每个数字在1≤ai≤100000，

第一行包含一个整数 n（(1 \leq n \leq 8000)），表示数字序列大小。第二行包含 n 个整数 (a_1, a_2, \ldots, a_n)，其中第 i 个整数 (a_i)（(1 \leq a_i \leq 100000)）为数字序列中元素的大小。

输出 n 行，其中第 i 行包含一个整数，表示当 (k = i) 时的最小值。