题目描述

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 $\textit{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 $n~(1 \leq n \leq 9)$. The second line contains $n$ space separated integers $s_i~(1 \leq s_i \leq 10^9)$.

输出格式

The output contains $n (n + 1) / 2$ integers in their own lines, the expectations when $k = 1, \ldots, n (n + 1) / 2$ multiplied by $n (n + 1) / 2$. It can be shown that the results are always integers.

题目大意

给出一个长度为 $n$ 的序列 $s$，定义 $C(l,r)=\sum\limits_{i=l}^r s_i$。

对于每个 $1 \le k \le n(n+1)/2$，找出 $k$ 个二元组 $(l_1,r_1),\dots,(l_k,r_k)$，满足 $1 \le l_i \le r_i \le n$，最小化：

$$\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] $$

您只需要对于每个 $k$ 输出对应的值，不需要输出方案。

1
1

0

2
13 24

26
13
0

3
6 4 7

33
21
12
8
4
0

提示

For the first test case, we only need to consider the case $k = 1$. We can only choose $l_1=r_1=1$. Then the expected loss is $C(1, 1) - C(1, 1) = 0$ and the result is $0 \times 1 \times (2) / 2 = 0$.

For the third test case, consider the case when $k = 3$. We choose $l_1=r_1=1$, $l_2=r_2=3$ and $l_3=1, r_3=3$. The expected loss is $2$. And the result is $2 \times 6 = 12$.