406087: GYM102263 I Bashar and Hamada

Bashar is a very smart person, he invented a new function $$$F(S)$$$, where $$$S$$$ is a multiset of integers.

The function $$$F(S)$$$ returns the sum of the absolute difference between every pair of elements in $$$S$$$.

For example $$$F($$${$$$3 , 3 , 1 , 7$$$}$$$)$$$ = $$$\vert 3 - 3 \vert$$$ + $$$\vert 3 - 1 \vert$$$ + $$$\vert 3 - 7 \vert$$$ + $$$\vert 3 - 1 \vert$$$ + $$$\vert 3 - 7 \vert$$$ + $$$\vert 1 - 7 \vert$$$ = $$$18$$$.

After that Bashar gave Hamada an array $$$a$$$ that contains $$$n$$$ integers, and asked him to solve this problem.

For 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.

Hamada couldn't solve the problem and he asked you for help.

The first line of input contains one integer $$$n$$$ $$$(2 \leq n \leq 3 \times 10 ^ {5})$$$ which is the size of array $$$a$$$.

The 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.

For every $$$k$$$ such that $$$(2 \leq k \leq n)$$$, print the maximum possible $$$F(S)$$$ of a subsequence of size $$$k$$$, starting from $$$k = 2$$$ ending at $$$k = n$$$.

3
1 7 5

6 12

a subsequence of size $$$k$$$ is a sequnece that can be obtained be removing $$$n-k$$$ integers from $$$a$$$.