HZNUOJ

与班尼特·胡迪一起做生意

Tags:
Time Limit:  3 s      Memory Limit:   256 MB
Submission:1250     AC:152     Score:90.86

Description

马爷作为2-80X的资深土财主,靠着敏锐的商业嗅觉不断买卖商品赚的盆满钵满。近日来大家发现了异样。马爷做生意从来只有赚钱,永远不会亏本。

坦诚的马爷公开了这个秘密。马爷早些年通过不可描述的手段弄到了一个可以预测价格的机器。通过它,马爷可以知道某个商品在今后n天的价格。但是作为牺牲,马爷在这n天之内最多只能分别进行一次该商品的买进和卖出

现在大家都知道了这个秘密。但是你真的可以选对时间买进卖出,使得自己的收益最大化吗?

Input

第一行为数字T,代表接下来有T组数据(T<=10)

每组数据第一行为数字N,代表知道N天的价格信息(N<=10^6)

每组数据第二行为N个正整数ai,ai代表第i天的价格(0<ai<10^9,1<=i<=N)。

Output

每组数据输出占一行,一行仅输出一个数字X,代表最多可以赚X元

(注意:买进一定在卖出之前)

Samples

input
3 5 1 2 3 4 5 5 1 2 3 1 5 5 5 4 3 2 1
output
4 4 0

Hint

样例一中在第1天买进第5天卖出可以赚4元

样例二中在第1天买进和第4天买进第5天卖出都可以赚4元,

样例三中在每天都在跌,怎么买都是亏钱,所以选择不买不卖

Author

YU, Deli

Source

杭州师范大学第十一届程序设计竞赛