P13215 [GCJ 2015 #1A] Mushroom Monster

Kaylin 喜欢蘑菇。只要把蘑菇放到她的盘子里，她就会把它们吃掉！在本题中，她正在吃一盘蘑菇，而 Bartholomew 会不断往她的盘子里加蘑菇。 我们每隔 $10$ 秒观察一次她盘子里的蘑菇数量。Bartholomew 可以在任何时刻往盘子里加任意个（非负整数）蘑菇，蘑菇离开盘子的唯一方式就是被 Kaylin 吃掉。 请你用两种不同的方法计算出 Kaylin 至少吃了多少个蘑菇： 1. 假设 Kaylin 可以在任何时刻吃掉任意数量的蘑菇。 2. 假设从第一次观察开始，只要盘子里有蘑菇，Kaylin 就以一个恒定的速度吃蘑菇。 例如，若输入为 $10$ $5$ $15$ $5$： 用第一种方法，Kaylin 至少吃了 $15$ 个蘑菇：她先吃掉 $5$ 个，然后 Bartholomew 又加了 $10$ 个蘑菇，然后她又吃掉了 $10$ 个。无论如何，她都不可能吃得更少。 用第二种方法，Kaylin 至少吃了 $25$ 个蘑菇。我们可以确定她吃蘑菇的速度至少为每秒 $1$ 个。她一开始盘子里有 $10$ 个蘑菇。在前 $10$ 秒内，她吃掉 $10$ 个蘑菇，Bartholomew 又加了 $5$ 个蘑菇。接下来的 $5$ 秒，她吃掉 $5$ 个蘑菇，然后盘子在 $5$ 秒内保持空，接着 Bartholomew 又加了 $15$ 个蘑菇。最后 $10$ 秒，她又吃掉了 $10$ 个蘑菇。

第一行输入一个整数 $T$，表示测试用例的数量。接下来有 $T$ 组测试数据。每组测试数据包含两行，第一行为一个整数 $N$，第二行为 $N$ 个用空格分隔的整数 $m_i$，表示 Kaylin 盘子里在每个 $10$ 秒时刻的蘑菇数量（包括初始时刻）。

对于每组测试数据，输出一行，格式为 "Case #$x$: $y$ $z$"，其中 $x$ 表示测试用例编号（从 $1$ 开始），$y$ 表示用第一种方法计算的 Kaylin 至少吃掉的蘑菇数量，$z$ 表示用第二种方法计算的 Kaylin 至少吃掉的蘑菇数量。

**数据范围** - $1 \leq T \leq 100$。 **小数据集（7 分）** - 时间限制：5 秒。 - $2 \leq N \leq 10$。 - $0 \leq m_i \leq 100$。 **大数据集（8 分）** - 时间限制：10 秒。 - $2 \leq N \leq 1000$。 - $0 \leq m_i \leq 10000$。 由 ChatGPT 4.1 翻译