{"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\u003eBashar is a very smart person, he invented a new function $$$F(S)$$$, where $$$S$$$ is a multiset of integers.\u003c/p\u003e\u003cp\u003eThe function $$$F(S)$$$ returns the sum of the absolute difference between every pair of elements in $$$S$$$.\u003c/p\u003e\u003cp\u003eFor example $$$F($$${$$$3 , 3 , 1 , 7$$$}$$$)$$$ \u003d $$$\\vert 3 - 3 \\vert$$$ + $$$\\vert 3 - 1 \\vert$$$ + $$$\\vert 3 - 7 \\vert$$$ + $$$\\vert 3 - 1 \\vert$$$ + $$$\\vert 3 - 7 \\vert$$$ + $$$\\vert 1 - 7 \\vert$$$ \u003d $$$18$$$.\u003c/p\u003e\u003cp\u003eAfter that Bashar gave Hamada an array $$$a$$$ that contains $$$n$$$ integers, and asked him to solve this problem.\u003c/p\u003e\u003cp\u003eFor every $$$k$$$ such that $$$(2 \\leq k \\leq n)$$$, Hamada should choose a subsequence of $$$k$$$ integers from $$$a$$$, such that $$$F(S)$$$ is maximised. \u003c/p\u003e\u003cp\u003eHamada couldn\u0027t solve the problem and he asked you for help.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of input contains one integer $$$n$$$ $$$(2 \\leq n \\leq 3 \\times 10 ^ {5})$$$ which is the size of array $$$a$$$.\u003c/p\u003e\u003cp\u003eThe second line contains $$$n$$$ integers, the $$$i^{th}$$$ one is $$$a_i$$$ $$$(1 \\leq a_i \\leq 10 ^ 8)$$$, which is the $$$i^{th}$$$ element in the array.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor every $$$k$$$ such that $$$(2 \\leq k \\leq n)$$$, print the maximum possible $$$F(S)$$$ of a subsequence of size $$$k$$$, starting from $$$k \u003d 2$$$ ending at $$$k \u003d n$$$.\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\u003e3\n1 7 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6 12\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\u003ea subsequence of size $$$k$$$ is a sequnece that can be obtained be removing $$$n-k$$$ integers from $$$a$$$.\u003c/p\u003e"}}]}