Minimizing Exam Loss via Optimal Power Cut Plans

Suppose you and your teammate Mixsx are scheduled to attend the Namomo Camp which lasts for \( n \) consecutive days. Day \( i \) has a cost of \( s_i \). Unfortunately, Mixsx has final exams on some consecutive days \( [L,R] \) (with \( 1 \le L \le R \le n \)); every such pair \( (L,R) \) is chosen with equal probability \( \frac{1}{n(n+1)/2} \). When Mixsx takes his exams (i.e. is absent from the camp from day \( L \) to day \( R \)), his loss is \( C(L,R)=\sum_{i=L}^{R} s_i \).

You want Mixsx to skip his exams and come to the camp. Before \( L \) and \( R \) are announced, you can prepare up to \( k \) plans. In the \( i\text{-th} \) plan you choose an interval \( [l_i, r_i] \) with \( 1\le l_i\le r_i\le n \) during which you shut off the electricity at his college. Once \( L \) and \( R \) are known, you can pick any one of your prepared plans \( x \) satisfying \( L\le l_x\le r_x\le R \). Then, Mixsx will attend the camp on days \( l_x \) to \( r_x \), effectively reducing his loss to \[ C(L,R) - C(l_x,r_x) = \sum_{i=L}^{R} s_i - \sum_{i=l_x}^{r_x} s_i. \] If no plan fits inside \( [L,R] \), his loss remains \( C(L,R) \).

Your goal is to choose the \( k \) plans (i.e. choose \( 2k \) integers \( l_1,\ldots, l_k,\, r_1,\ldots,r_k \) with \( 1\le l_i\le r_i\le n \)) to minimize the expected loss of Mixsx. Formally, define the overall loss if the plans are chosen as

[ \sum_{1\le L\le R\le n}\Bigl(C(L,R)-\max_{1\le i\le k,; L\le l_i\le r_i\le R} C(l_i,r_i)\Bigr), ]

where \( \max_{1\le i\le k,\; L\le l_i\le r_i\le R} C(l_i,r_i) \) is taken to be \(0\) if no plan \( i \) satisfies \( L\le l_i\le r_i\le R \).

You are to compute, for each \( k=1,2,\dots,\,\frac{n(n+1)}{2} \) (the total number of possible intervals), the minimized sum above. However, instead of outputting a fraction, print the value multiplied by \( n(n+1)/2 \) (which is the total number of possible \( (L,R) \) pairs).

Input Format:

n
s₁ s₂ … sₙ

Output Format:

ans₁ ans₂ … ansₘ

Here, \( m = n(n+1)/2 \). The \( k\text{-th} \) output number is the minimized total loss multiplied by \( \frac{n(n+1)}{2} \) when you optimally choose \( k \) plans.

inputFormat

The first line contains an integer \( n \) indicating the number of days of the Namomo Camp. The second line contains \( n \) integers \( s_1,s_2,\dots,s_n \) where \( s_i \) is the cost on day \( i \).

outputFormat

Output \( m = n(n+1)/2 \) space‐separated integers. The \( k\text{-th} \) integer corresponds to the minimized total loss (summed over all exam intervals) multiplied by \( n(n+1)/2 \), if you choose the \( k \) plans optimally.

sample

3
1 2 3

30 30 30 30 30 0