Trapping Rain Water

Given an array representing the elevation map where the width of each bar is 1, compute how much water it is able to trap after it rains. For each index i, the water that can be trapped is computed using the formula:

$$w_i = \min(L_i, R_i) - h_i$$

where:

• $$h_i$$ is the height at index i,
• $$L_i$$ is the maximum height to the left of index i (including i itself), and
• $$R_i$$ is the maximum height to the right of index i (including i itself).

You will be given multiple test cases. For each test case, output the total amount of water trapped as a single integer on a new line.

inputFormat

The input begins with an integer T (the number of test cases). For each test case, the first line contains an integer n denoting the number of bars. The following line contains n space-separated integers representing the elevation map.

For example:

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

outputFormat

For each test case, output a single line with an integer representing the total volume of trapped water.

## sample

1
5
3 2 1 2 3

4

</p>