Trapping Rain Water

Given an array of non-negative integers representing the heights of vertical pillars, your task is to compute the maximum amount of water that can be trapped between the pillars after it rains.

Water is trapped between two pillars if there is a valley between them. For each pillar i, the water above it is computed using the formula:

where:

• \(h_i\) is the height of the i-th pillar,
• \(\text{left}_i\) is the maximum height among the pillars to the left of pillar i,
• \(\text{right}_i\) is the maximum height among the pillars to the right of pillar i.

The total trapped water is the sum of water above every pillar. If no water can be trapped, the answer is 0.

inputFormat

The first line of input contains a single integer T, representing the number of test cases. For each test case, the first line contains an integer n, the number of pillars. The second line contains n space-separated non-negative integers denoting the heights of the pillars.

outputFormat

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

4
12
0 1 0 2 1 0 1 3 2 1 2 1
6
4 2 0 3 2 5
7
7 4 0 9 4 7 8
5
0 0 0 0 0

6
9
15
0