One day on a rainy morning, Tahura was enjoying a cup of tea on her balcony when she noticed that some bricks were laying on the waterway trapping the rainwater that the waterway was supposed to drain. All the bricks were square-shaped and some were stacked on top of another. Now she wanted to see how much water it can trap after it had rained for several hours.
She made a few assumptions —
- The drain has infinite depth.
- The width of each brick is $$$1$$$.
- The water beyond the ends on both sides of the brick structure is discarded. More specifically she only measured the water trapped between the first and the last brick.
Then she represented the brick structure with an array of integers. Each element of the array represents a stack of bricks and equals the number of bricks in that stack.
If The elevation map of the brick structure looked like this, the corresponding array would look like $$$[0,1,0,2,1,0,1,3,2,1,2,1]$$$.
Given the array representing the elevation map, can you find the maximum amount of water that could be trapped in the brick structure for her?
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ $$$\left(1 \leq n \leq 2 \cdot 10^4\right)$$$ — the length of the array.
The second line of each test case contains $$$n$$$ integers $$$h_i$$$ $$$(0 \leq h_i \leq 10^5)$$$ — the elevation array.
It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^4$$$.
For each test case, output the maximum amount of water that could be trapped by the elevated brick structure.
2120 1 0 2 1 0 1 3 2 1 2 164 2 0 3 2 5
6 9
