Fountains

题号：NC214901
时间限制：C/C++/Rust/Pascal 6秒，其他语言12秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

Suppose you and your teammate Mixsx will attend the Namomo Camp. The Namomo Camp will happen in ${n}$ consecutive days. We name the ${i}$ -th day as day ${i}$ ( $1\le i\le n$ ). The cost of day ${i}$ is $s_i$ .

Unfortunately, the schedule of the Namomo Camp conflicts with Mixsx's final exams. Mixsx has final exams every day between day ${L}$ and day ${R}$ . The exact value of ${L}$ and ${R}$ have not been announced by his college so we assume that every pair of integers ${L}$ and ${R}$ satisfying $1\le L\le R\le n$ will be chosen with probability ${1/(n(n+1)/2)}$ . He decides to take all the exams and thus be absent from the Namomo Camp from day ${L}$ to day ${R}$ . His loss will be $\sum_{i=L}^R s_i$ in this case.

As Mixsx's teammate, you want Mixsx to give up his final exams and come back to the Namomo Camp. You can prepare ${k}$ plans before ${L}$ and ${R}$ are announced. In the ${i}$ -th plan ( $1\le i\le k$ ), you shut the electricity off to his college every day from day $l_i$ to day $r_i$ . You can choose the values of $l_i$ and $r_i$ as long as they are two integers satisfying $1\le l_i\le r_i\le n$ .

Once ${L}$ and ${R}$ are announced, you can choose a plan ${x}$ ( $1\le x\le k$ ) such that $L\le l_x\le r_x\le R$ . Then Mixsx will come back to the Namomo Camp on every day from day $l_x$ to day $r_x$ . His loss becomes $\sum_{i=L}^R s_i-\sum_{i=l_x}^{r_x} s_i$ in this case. You will choose a plan that minimizes Mixsx's loss. If no plan ${x}$ satisfies $L\le l_x\le r_x\le R$ , Mixsx will attend his final exams normally and his loss is $\sum_{i=L}^R s_i$ .

Please calculate the minimum possible expected loss $ans_k$ of Mixsx if you choose the ${k}$ plans optimally. Output $ans_k\cdot n(n+1)/2$ for every ${k}$ from 1 to ${n(n+1)/2}$ .

Formally, given a list of ${n}$ numbers $s_i\ (1 \leq i \leq n)$ , define a loss function $C(L, R) = \sum_{i=L}^R s_i$ . Given an integer ${k}$ ( $1 \leq k \leq n (n + 1) / 2$ ), you should select ${2k}$ integers $l_1, \ldots, l_k, r_1,\ldots, r_k$ satisfying $1\le l_i\le r_i\le n$ for all $1 \leq i \leq k$ , such that

$\sum_{1\leq L\leq R\leq n} \left[C(L, R) - \max_{1\le i\le k, L \leq l_i \leq r_i \leq R} C(l_i, r_i) \right]$

is minimized. ( $\max_{1\le i\le k, L \leq l_i \leq r_i \leq R} C(l_i, r_i)$ is defined as 0 if no ${i}$ satisfies $1\le i\le k$ and $L \leq l_i \leq r_i \leq R$ .) Output the minimized value for every integer ${k}$ in ${[1, n(n + 1) / 2]}$ .

输入描述:

The first line contains an integer . The second line contains  space separated integers .

输出描述:

The output contains  integers in their own lines, the expectations when  multiplied by . It can be shown that the results are always integers.

示例1

输入

复制

1
1

输出

复制

说明

For the first test case, we only need to consider the case . We can only choose . Then the expected loss is  and the result is .

示例2

输入

复制

2
13 24

输出

复制

26
13
0

示例3

输入

复制

3
6 4 7

输出

复制

说明

For the third test case, consider the case when . We choose ,  and . The expected loss is 2. And the result is .