Problem Description

Given a sequence \( s \) of length \( n \), define \( C(l, r) = \sum_{i=l}^r s_i \).

For each \( 1 \le k \le \frac{n(n+1)}{2} \), find \( k \) pairs \((l_1, r_1), \dots, (l_k, r_k)\) such that \( 1 \le l_i \le r_i \le n \), to minimize:

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

You only need to output the corresponding value for each \( k \), not the solution.

Input Format

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 \)).

Output Format

The output contains \( \frac{n(n+1)}{2} \) integers, each on a new line, representing the expectations when \( k = 1, \ldots, \frac{n(n+1)}{2} \), multiplied by \( \frac{n(n+1)}{2} \). It can be shown that the results are always integers.

Sample Input and Output

Sample Input #1

1
1

Sample Output #1

0

Sample Input #2

2
13 24

Sample Output #2

26
13
0

Sample Input #3

3
6 4 7

Sample Output #3

33
21
12
8
4
0

Notes

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 部分

见题面 Output 部分