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 <= i <= 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 <= L <= R <= 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 <= i <= 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 <= l_i <= r_i <= n$.
Once $L$ and $R$ are announced, you can choose a plan $x$ ($1 <= x <= k$) such that $L <= l_x <= r_x <= 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 <= l_x <= r_x <= 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 $a n s_k$ of Mixsx if you choose the $k$ plans optimally. Output $a n s_k dot.op n (n + 1) \/ 2$ for every $k$ from $1$ to $n (n + 1) \/ 2$.
Formally, given a list of $n$ numbers $s_i$ $(1 <= i <= n)$, define a loss function $C (L, R) = sum_{i = L}^R s_i$. Given an integer $k$ ($1 <= k <= n (n + 1) \/ 2$), you should select $2 k$ integers $l_1, \\dots, l_k, r_1, \\dots, r_k$ satisfying $1 <= l_i <= r_i <= n$ for all $1 <= i <= 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 <= i <= k comma L <= l_i <= r_i <= R) C (l_i, r_i)$ is defined as $0$ if no $i$ satisfies $1 <= i <= k$ and $L <= l_i <= r_i <= R$.) Output the minimized value for every integer $k$ in $[ 1, n (n + 1) \/ 2 ]$.
The first line contains an integer $n med (1 <= n <= 9)$. The second line contains $n$ space separated integers $s_i med (1 <= s_i <= 10^9)$.
The output contains $n (n + 1) \/ 2$ integers in their own lines, the expectations when $k = 1, \\dots, n (n + 1) \/ 2$ multiplied by $n (n + 1) \/ 2$. It can be shown that the results are always integers.
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$.
## Input
The first line contains an integer $n med (1 <= n <= 9)$. The second line contains $n$ space separated integers $s_i med (1 <= s_i <= 10^9)$.
## Output
The output contains $n (n + 1) \/ 2$ integers in their own lines, the expectations when $k = 1, \\dots, n (n + 1) \/ 2$ multiplied by $n (n + 1) \/ 2$. It can be shown that the results are always integers.
[samples]
## Note
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$.
**Definitions**
Let $ n \in \mathbb{Z}^+ $, $ s = (s_1, s_2, \dots, s_n) \in \mathbb{Z}^n $ with $ s_i \geq 1 $.
Let $ \mathcal{I} = \{ (l, r) \in \mathbb{Z}^2 \mid 1 \leq l \leq r \leq n \} $, the set of all contiguous subarrays.
Let $ C(l, r) = \sum_{i=l}^r s_i $ for $ (l, r) \in \mathcal{I} $.
Let $ |\mathcal{I}| = \frac{n(n+1)}{2} $.
**Constraints**
For each $ k \in \left[1, \frac{n(n+1)}{2}\right] $, select $ k $ intervals $ \{(l_i, r_i)\}_{i=1}^k \subseteq \mathcal{I} $ (possibly with repetition).
**Objective**
For each $ k $, minimize:
$$
\sum_{(L,R) \in \mathcal{I}} \left[ C(L, R) - \max_{\substack{1 \leq i \leq k \\ L \leq l_i \leq r_i \leq R}} C(l_i, r_i) \right]
$$
where the maximum is defined as 0 if no $ i $ satisfies $ L \leq l_i \leq r_i \leq R $.
Output the minimized value for each $ k = 1, 2, \dots, \frac{n(n+1)}{2} $.