程序设计能力实训

1251. 小巴菲特买股票

单点时限: 2.0 sec

内存限制: 256 MB

股神巴菲特在小时候就极具投资天赋。当时他手上有一些资金,想去股票市场做做交易。

给出一支股票在 $N$ 天之内每天的交易价格,假设每天的交易价格唯一且一定能成交,不需要任何手续费等其他费用,并且小巴菲特的初始资金量充足。

规定小巴菲特$N $天之内只能且必须先买一股然后卖一股,两次交易可以在同一天完成也可以不在同一天完成。

请帮小巴菲特计算出 $N$ 天之后最多能赚多少钱?

输入格式

第 1 行:一个整数 $T$ ($1 \le T \le 10$) 为问题数。

对于每组测试数据:

第 1 行是 1 个正整数:天数 N ( $0\lt n\le 500$ )。

第 2 行 N 个正整数,每个正整数 $X_i$($0\lt i≤N$, $0 \lt x_i ≤10000$) 表示第 $i$ 天该股票每股的交易价格。

</n<></n<>

输出格式

对于每个问题,输出一行问题的编号(0 开始编号,格式:case #0: 等)。然后在一行输出小巴菲特最多能赚的钱数。

样例

Input
3
6
9 6 5 4 2 1
5
9 23 1 3 1
60
4326 4775 3962 5995 6045 6906 6539 7789 7874 3923 8134 2269 582 7872 8255 7577 7176 8534 2460 4451 7464 8690 2168 5564 7774 2060 5106 6974 268 304 7179 8560 193 6656 7968 118 2751 3204 2981 200 64 932 9155 1140 2052 7543 738 4230 9758 6925 5275 2678 5809 3754 199 9539 1172 2643 6572 7890
Output
case #0:
0
case #1:
14
case #2:
9694
不限期开放

题目列表