In the city of Delhi, rain in pouring down heavily. But thanks to Inspector Gordon, now the city has best rainwater harvesting system. The vacant spaces between two building acts as water container. The height of buildings differs, hence the container can hold amount of water which is equal to the height of smaller building.

Given the number of buildings and height of each building, calculate the maximum amount of water that can be collected in all the containers.

Input format :-

The first line contains t number of test cases.

For each test case there is two lines of input, first line consisting of the integer N – which denotes the number of buildings in the city. Second line consisting N separate space positive integers which denotes the height of each building.

Constraints :-

1 <= t <= 100

1 <= N <= 10^5

1 <= a[i] <= 10^9

Output Format :-

Final output is t lines containing the result for each input test case.

CommentsNo comment yet.