Given an array of n integers, consider pairings of k pairs. Each number can appear in at most one pair, and the cost of a pair (a,b) is |a-b|. The cost of a pairing is the sum of all costs of the pairs.

Calculate the minimum costs of pairings for k=1,2,\dots,\lfloor n/2 \rfloor.

Input

The first line has an integer: the array size.

The next line has n integers x_1,x_2,\dots,x_n: the array contents.

Output

Print \lfloor n/2 \rfloor integers: the minimum costs of pairings.

Constraints

• 2 \le n \le 2 \cdot 10^5
• 1 \le x_i \le 10^9

Example

Input:

8
3 1 2 7 9 3 4 7

Output:

0 0 1 6

Explanation: Possible minimum-cost pairings are [(3,3)], [(3,3),(7,7)], [(1,2),(3,3),(7,7)] and [(1,2),(3,3),(4,7),(7,9)].