{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eSuppose 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$$$. \u003c/p\u003e\u003cp\u003eUnfortunately, the schedule of the Namomo Camp conflicts with Mixsx\u0027s 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 \u003cspan class\u003d\"tex-font-style-it\"\u003eloss\u003c/span\u003e will be $$$\\sum_{i\u003dL}^R s_i$$$ in this case. \u003c/p\u003e\u003cp\u003eAs Mixsx\u0027s 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$$$.\u003c/p\u003e\u003cp\u003eOnce $$$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\u003dL}^R s_i-\\sum_{i\u003dl_x}^{r_x} s_i$$$ in this case. You will choose a plan that minimizes Mixsx\u0027s 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\u003dL}^R s_i$$$.\u003c/p\u003e\u003cp\u003ePlease 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$$$.\u003c/p\u003e\u003cp\u003eFormally, given a list of $$$n$$$ numbers $$$s_i$$$ $$$(1 \\leq i \\leq n)$$$, define a loss function $$$C(L, R) \u003d \\sum_{i\u003dL}^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\u003c/p\u003e\u003cp\u003e$$$$$$\\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]$$$$$$\u003c/p\u003e\u003cp\u003e 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]$$$. \u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe 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)$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eThe output contains $$$n (n + 1) / 2$$$ integers in their own lines, the expectations when $$$k \u003d 1, \\ldots, n (n + 1) / 2$$$ multiplied by $$$n (n + 1) / 2$$$. It can be shown that the results are always integers.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n13 24\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e26\n13\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n6 4 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e33\n21\n12\n8\n4\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eFor the first test case, we only need to consider the case $$$k \u003d 1$$$. We can only choose $$$l_1\u003dr_1\u003d1$$$. Then the expected loss is $$$C(1, 1) - C(1, 1) \u003d 0$$$ and the result is $$$0 \\times 1 \\times (2) / 2 \u003d 0$$$.\u003c/p\u003e\u003cp\u003eFor the third test case, consider the case when $$$k \u003d 3$$$. We choose $$$l_1\u003dr_1\u003d1$$$, $$$l_2\u003dr_2\u003d3$$$ and $$$l_3\u003d1, r_3\u003d3$$$. The expected loss is $$$2$$$. And the result is $$$2 \\times 6 \u003d 12$$$.\u003c/p\u003e"}}]}