P6345 [CCO 2017] 接雨滴

晚上，夜黑风高，大雨疯狂地从天而降。 Lucy 想要接住一些雨滴，但她只有有限的工具。她有一套不同高度的柱子来接住雨滴。每根柱子的高度为整数，宽度为 $1$。她排列好柱子之后，就会用其他器具夹紧柱子，来让雨滴顺利地储存在柱子的间隙里。你可以认为雨滴的数量是无限的。 举个例子，如果 Lucy 有高度分别为 $(1,5,2,1,4)$ 的五根柱子，她可以这样排列柱子。 ``` * * * * * ** * ***** ``` 这样会接住 $5r$ 雨滴（$r$ 代表 $1$ 个单位的雨滴）。 **为了方便表述，我们定义 $r$ 为雨滴的单位。** ``` * *RR* *RR* **R* ***** ``` 当然了，她也可以这样摆放柱子，这样可以接住 $6r$ 雨滴。 ``` * *RR* *RR* **RR* ***** ``` 再举一个例子，如果柱子的高度分别为 $(5,1,5,1,5)$，Lucy 可以接住 $8r$ 雨滴。 ``` *R*R* *R*R* *R*R* *R*R* ***** ``` 最后一个例子，如果柱子的高度分别为 $(5,1,4,1,5)$，她可以接住 $9r$ 雨滴。 ``` *RRR* *R*R* *R*R* *R*R* ***** ``` Lucy 有 $n$ 个高度为 $h_1,h_2,...,h_n$ 的柱子。她想知道，在所有可能的摆放方案中，所有可能的雨滴量（以 $r$ 为单位）是多少。（具体可看样例解释）

无

无

#### 样例解释 参见上文的三个例子。 #### 数据范围及约定 **本题采用多测试点捆绑测试，共有 $3$ 个子任务。** - 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$。 对于全部的测试点，保证 $2 \le n \le 500$，$1 \le h_i \le 50$。 来源：[CCO 2017](https://cemc.math.uwaterloo.ca/contests/computing/2017/) Day2「[Rainfall Capture](https://cemc.math.uwaterloo.ca/contests/computing/2017/stage%202/day2.pdf)」。 说明：翻译来自 [LOJ](https://loj.ac/problem/2753)。