Description

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$ 个蘑菇。

Input Format

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

Output Format

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

4
4
10 5 15 5
2
100 100
8
81 81 81 81 81 81 81 0
6
23 90 40 0 100 9

Case #1: 15 25
Case #2: 0 0
Case #3: 81 567
Case #4: 181 244

Hint

数据范围

• $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 翻译