文理学院程序设计在线练习


魔仙堡要被水淹啦???

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 25   Accepted Submission(s): 11
Problem Description

小蓝作为魔仙堡的守护魔仙,在第1次魔仙堡大战后,便从此隐居。原本平静祥和的魔仙堡,却迎来了魔仙历史中最大的一次暴雨,一些低矮的魔仙城市,瞬间被淹没其中。小蓝在得知此事后,急忙出山。发动魔法想要将积水抽完,却遇到了一个难题,由于魔仙城市太大了,无法统计积水的数量,而该魔法必须精确的设定吸水量才能成功吸水。
亲爱的小魔仙们,你们能算出积水量,拯救魔仙堡吗?
假设魔仙堡中的所有城市都在一条直线上,且均为长宽为1,高度未知的长方体。

Input

第一行是一个整数T,表示测试的组数(1<=T<=1000),下一行是一个整数N,表示魔仙城市的数量(1<=N<=100000),接下来一行N 个整数,表示魔仙城市的高度H(0<=H<=1000)

Output

每组测试数据输出一个值:需要抽取的水量

Sample Input
1
12
0 1 0 2 1 0 1 3 2 1 2 1
Sample Output
6
Hint



Source

2018元培院赛