Trapping Rain Water

You are given an elevation map represented by a sequence of non-negative integers where each integer corresponds to the height of a bar. The width of each bar is 1. Compute how much water can be trapped after raining.

Formally, given an integer n and an array heights of length n, the amount of water that can be trapped is determined by the formula

\( \text{Water}_i = \min(L_i, R_i) - heights[i] \)

where \(L_i\) is the maximum height to the left of index \(i\) (including \(i\)) and \(R_i\) is the maximum height to the right of index \(i\) (including \(i\)). Sum the water above each bar to obtain the total amount of trapped water.

Your program should read the input from standard input and print the results to standard output.

inputFormat

The first line contains an integer t, representing the number of test cases. Each test case is described as follows:

• The first line of each test case contains an integer n, the number of bars.
• The second line contains n space-separated non-negative integers representing the heights of the bars.

outputFormat

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

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

6