Trapping Rain Water

You are given an array of non-negative integers representing the height of columns. After it rains, water gets trapped between these columns. The water trapped at index (i) can be computed as (\max(0, \min(L_{max},R_{max}) - h_i)), where (L_{max}) and (R_{max}) are the maximum heights to the left and right of index (i), respectively.

Given (T) test cases, for each test case you are provided an integer (N) denoting the number of columns, followed by (N) space-separated non-negative integers representing the heights. Your task is to compute the maximum amount of water that can be trapped for each test case and output the result on a separate line.

inputFormat

The input begins with an integer (T) representing the number of test cases. For each test case, the first line contains an integer (N) — the number of columns. The following line contains (N) space-separated integers representing the heights of the columns.

outputFormat

For each test case, output a single line containing the computed maximum amount of water that can be trapped.## sample

3
12
0 1 0 2 1 0 1 3 2 1 2 1
6
4 2 0 3 2 5
6
1 0 1 0 1 0

6
9
2