Description

At night, it is pitch-dark and windy, and heavy rain is pouring down from the sky.

Lucy wants to catch some raindrops, but she only has limited tools. She has a set of pillars of different heights to catch raindrops. Each pillar has an integer height and width $1$. After she arranges the pillars, she will use other tools to clamp them together, so that raindrops can be stored smoothly in the gaps between the pillars. You may assume the amount of rain is infinite.

For example, if Lucy has five pillars with heights $(1,5,2,1,4)$, she can arrange them like this:

 *   
 *  *
 *  *
 ** *
*****

This will catch $5r$ raindrops ($r$ represents one unit of raindrops).

For convenience, we define $r$ as the unit of raindrops.

 *   
 *RR*
 *RR*
 **R*
*****

Of course, she can also arrange them like this, which will catch $6r$ raindrops:

 *   
 *RR*
 *RR*
**RR*
*****

As another example, if the pillar heights are $(5,1,5,1,5)$, Lucy can catch $8r$ raindrops:

*R*R*
*R*R*
*R*R*
*R*R*
*****

In the last example, if the pillar heights are $(5,1,4,1,5)$, she can catch $9r$ raindrops:

*RRR*
*R*R*
*R*R*
*R*R*
*****

Lucy has $n$ pillars with heights $h_1,h_2,\ldots,h_n$. She wants to know, among all possible arrangements, all possible amounts of raindrops that can be caught (measured in units of $r$). (See the sample explanation for details.)

Input Format

The first line contains an integer $n$, the number of pillars.

The second line contains $n$ integers $h_i$, the heights of the pillars.

Output Format

Output a single line. Print all possible numbers of raindrops that can be caught (in units of $r$) in increasing order.

5
1 5 2 1 4

0 1 2 3 4 5 6 8 

5
5 1 5 1 5

0 4 8

5
5 1 4 1 5

0 1 3 4 5 6 7 8 9

Hint

Sample Explanation

See the three examples above.

Constraints and Notes

This problem uses bundled testdata, with a total of $3$ subtasks.

• Subtask 1 (20 points): $2 \le n \le 10$.
• Subtask 2 (40 points): $2 \le n \le 50$.
• Subtask 3 (40 points): $2 \le n \le 500$, $1 \le h_i \le 50$.

For all testdata, it is guaranteed that $2 \le n \le 500$ and $1 \le h_i \le 50$.

Source: CCO 2017 Day 2 “Rainfall Capture”.

Note: This translation is from LOJ.

Translated by ChatGPT 5