0 Judge
Code: 0
Recently, Lubrige made some $1 \times N$ sized aquariums. They are special because the bottoms are not flat. Lubrige is curious about how much water they are able to trap after filling. For example, the aquarium in the following graph can trap 6 units of water (the blue part).
The first line of the input contains an integer $T$ ($1 \leq T \leq 1000$), the number of test cases. Each test case is formatted as follows.
$N\;c_{1}\;c_{2}\;\cdots\;c_{N}$
There is only one line of input per test case beginning with an integer $N$ ($1 \leq N \leq 10000$), followed by $N$ integers $c_{1}\;c_{2}\;\cdots\;c_{N}$ ($0 \leq c_{i} \leq 30000$ for all $1 \leq i \leq N$) representing the heights of the bottom of the aquarium.
For each test case, output an integer, which denotes the maximum number of units of water that could be trapped, in a line.
2
3 2 1 2
11 1 0 2 1 0 1 3 2 1 2 1
1
6
no