Canadian Computing Olympiad: 2017 Day 2, Problem 1

It was a dark and stormy night. It also rained, and rained, and rained.

Lucy wants to capture some of the rain, but she only has limited materials. She has a collection of pillars of various heights, which she can configure to capture the rain. Each pillar has an integer height and has a length and width of $1$. Once Lucy has her configuration of pillars, she has enough other siding material to enclose the front and back to allow rain to fill all the available space in between pillars. There is more than enough rain and any excess rain will overflow and get absorbed into the earth.

For example, if Lucy has pillars of height $1,5,2,1,4$, she could configure them as follows (all configurations are illustrated from the side):

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

which would capture $5$ units of rain (R) as follows:

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

For this first collection of pillars $(1,5,2,1,4)$, she could also capture $6$ units of rain as follows:

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

As another example, if the collection of pillars was $5,1,5,1,5$, Lucy could capture $8$ units of rain as follows:

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

Finally, this configuration of $(5,1,4,1,5)$ captures $9$ units of rain:

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

Lucy has $N$ pillars $(2\le N\le 500)$ with heights $h_1,h_2,\dots ,h_N$ $(1\le h_i\le 50)$. She would like to know, of all possible configurations of pillars, what are all of the obtainable volumes of rainfall that she can capture using these $N$ pillars.

Input Specification

The first line contains the integer $N$ $(2\le N\le 500)$ signifying the number of pillars. The next line contains the integers $h_i$ $(1\le h_i\le 50,1\le i\le N)$, representing the $i$th pillar's height.

For 5 of the 25 marks available, $N\le 10$.
For an additional 10 of the 25 marks available, $N\le 50$.

Output Specification

On one line, output a space-separated list of all possible obtainable integer volumes of rain captured, in increasing order.

Sample Input 1

5
1 5 2 1 4

Sample Output 1

0 1 2 3 4 5 6 8

Explanation for Sample Output 1

This is the first given example.

Sample Input 2

5
5 1 5 1 5

Sample Output 2

0 4 8

Explanation for Sample Output 2

This is the second given example.

Sample Input 3

5
5 1 4 1 5

Sample Output 3

0 1 3 4 5 6 7 8 9

Explanation for Sample Output 3

This is the third given example.