那是一个黑暗而风雨交加的夜晚。雨一直在下，下个不停。

Lucy 想要收集一些雨水，但她手头的材料有限。她有一组高度各异的柱子，她可以将这些柱子排列起来以收集雨水。每根柱子的高度都是一个整数，长度和宽度均为 1。一旦 Lucy 排列好了柱子，她就有足够的侧边材料来封闭前后，从而让雨水填满柱子之间的所有可用空间。雨水非常充足，任何多余的雨水都会溢出并被大地吸收。

例如，如果 Lucy 有高度为 1, 5, 2, 1, 4 的柱子，她可以将它们排列如下（所有排列均从侧面展示）：

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

这可以收集 5 单位的雨水 (R)，如下所示：

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

对于这组柱子 (1, 5, 2, 1, 4)，她还可以收集 6 单位的雨水，如下所示：

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

作为另一个例子，如果柱子集合为 5, 1, 5, 1, 5，Lucy 可以收集 8 单位的雨水，如下所示：

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

最后，这种 (5, 1, 4, 1, 5) 的排列可以收集 9 单位的雨水：

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

Lucy 有 $N$ 根柱子 ($2 \le N \le 500$)，高度分别为 $h_1, h_2 \dots h_N$ ($1 \le h_i \le 50$)。她想知道，在所有可能的柱子排列方式中，她利用这 $N$ 根柱子所能收集到的雨水体积的所有可能取值。

输入格式

第一行包含一个整数 $N$ ($2 \le N \le 500$)，表示柱子的数量。下一行包含整数 $h_i$ ($1 \le h_i \le 50, 1 \le i \le N$)，表示第 $i$ 根柱子的高度。

子任务

在总分 25 分中，有 5 分满足 $N \le 10$。 在总分 25 分中，另有 10 分满足 $N \le 50$。

输出格式

在一行中，按升序输出所有可能收集到的整数雨水体积，并用空格分隔。

样例

输入 1

5
1 5 2 1 4

输出 1

0 1 2 3 4 5 6 8

说明 1

这是第一个给出的例子。

输入 2

5
5 1 5 1 5

输出 2

0 4 8

说明 2

这是第二个给出的例子。

输入 3

5
5 1 4 1 5

输出 3

0 1 3 4 5 6 7 8 9

说明 3

这是第三个给出的例子。