Trapping Rain Water

Given an array of non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The water trapped at index i can be computed as:

$$water_i = \max\Big(\min(leftMax_i, rightMax_i) - height_i,\ 0\Big)$$

where:

• $$leftMax_i$$ is the maximum height to the left of index i (including the current bar),
• $$rightMax_i$$ is the maximum height to the right of index i (including the current bar).

Your task is to calculate the total amount of water that can be trapped after raining for each test case.

inputFormat

The input is read from stdin and has the following format:

T
N1
h1 h2 ... hN1
N2
h1 h2 ... hN2
...
NT
h1 h2 ... hNT

where:

• T is the number of test cases.
• For each test case, the first line contains an integer N, the number of buildings.
• The next line contains N space-separated non-negative integers representing the heights of the buildings.

outputFormat

For each test case, output a single line from stdout containing one integer: the maximum amount of water that is trapped for that case.

## sample

1
12
0 1 0 2 1 0 1 3 2 1 2 1

6

</p>