Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
Statistics

题目描述

机房准备进购一批统一型号的水杯。但每个人对于水杯容量的需求不一样。比如小 Y 喜欢超大容量的水杯,小 Z 则喜欢普通的小钢杯。

幸运的是,这种水杯可以由购买者自己组装出不同容量。具体地,这批水杯是一种 二维水杯,由 $n$ 根二维的柱子组成,第 $i$ 根柱子高 $h_i$ 个单位,宽 $1$ 个单位。购买者可以通过重新排列这 $n$ 根二维柱子来组装成不同的容量。

对于一种排列方案,假设有两根柱子 $h_l$, $h_r$,若 $l < i < r$,那么柱子 $i$ 上方就至少可以积 $\max(0, \min(h_l, h_r) − h_i)$ 平方单位的水。

*
*W*
*W*W*W*
********

举个例子,上图一共有 $8$ 根柱子(用 * 表示),按图示方式排列后可以装 $4$ 平方单位的水。图中 W 所示的是能盛水的位置。请注意,最右边的柱子由于右边没有更高的柱子,因此无法盛水。

现在小 Y 很好奇,这种神奇的水杯可以组装出哪些不同的容量呢?

输入格式

第一行读入一个 $n$ 表示这种水杯包含的柱子数量。

接下来一行 $n$ 个整数表示每一根柱子的高度。

输出格式

仅一行从小到大输出 $cnt$ 个整数,表示可能组装出的容量大小。

样例输入 1

8
4 1 3 1 2 1 2 1

样例输出 1

0 1 2 3 4 5 6 7 8 9 10

样例输入 2

10
50 50 2 2 2 1 2 1 2 2

样例输出 2

0 1 2 48 49 50 96 97 98 144 145 146 192 193 194 240 241 242 288 289 290 337 338 386

样例 1 解释

对于第一个样例,按输入顺序排列即为题中图示的情况,可以盛 4 平方单位的水。

特别地,将这些柱子按 4 1 1 1 1 2 2 3 排列可以得到最大的容量 $10$。可以证明 $[0, 10]$ 之间的整数容量都是能够达到的。

测试点约束

对于所有测试点满足:$2 \leq n \leq 500 , 1 \leq h_i \leq 50$。

本题开启捆绑评测,每个子任务约束如下:

子任务编号 $n\leq$ 分值
1 10 20
2 50 40
3 500 40