Aquariums

題目敘述

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

提示

Judge Setting

run-time limit: 1500 ms
memory limit: 262144 byte
測資數量: 0