Distinct Rainwater Volumes

Lucy has n pillars with integer heights. When it rains, she wants to catch as many raindrops as possible using her pillars. After arranging the pillars in a row, she uses external clamps to hold them in place so that water gets trapped in the "pockets" between the pillars. The amount of water (in units of r) collected by an arrangement is computed as follows.

Imagine the pillars are placed in a row. For each position i (0-indexed), define

\(L_i = \max\{a_0,a_1,\dots,a_i\}\quad\text{and}\quad R_i = \max\{a_i,a_{i+1},\dots,a_{n-1}\}\, .\)

Then the water stored above pillar i is \[ w_i = \max\bigl(\min(L_i,R_i) - a_i,\,0\bigr)\,. \] Thus, the total water trapped is \[ W = \sum_{i=0}^{n-1} w_i\,. \]

Lucy can rearrange the pillars arbitrarily (i.e. consider all permutations of the given pillars). Your task is to determine all distinct total water volumes (in units of r) that can be obtained among all possible arrangements.

Note: The clamp prevents water from spilling even if the natural boundaries are low; the above formula is the standard way to compute the trapped water when the pillar heights are given in order.

inputFormat

The first line contains a positive integer n (the number of pillars).
The second line contains n integers h₁, h₂, ..., h_n representing the heights of the pillars.

outputFormat

Output a single line containing all distinct total water volumes (in units of r) that can be obtained by some arrangement of the pillars. The values should be printed in ascending order and separated by a space.

sample

3
1 2 3

0 1