시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 21 | 10 | 9 | 50.000% |
In a big city, there are N walls arrange in a line from west to east, numbered by 1st to Nth. The walls are well designed and water-proof so water cannot pass through each wall. Unfortunately, it was raining heavily last week and the whole city had flooded by this heavy rain. The governor wants to put a super strong water pump to drain water as much as possible. He asks you to calculate maximum amount of water could be pumped out by a water pump.
Example
Suppose a line of walls in the city is shown as figure below.
After flooding by the heavy rain, water will be remained inside each pair of walls.
If the water pump is placed at the arrow marker, it can drain 7 units of water from the city.
However, one of the best positions to place the water pump is shown below at the arrow marker. 9 units of water would be drained.
Given heights of all walls, you task is to calculate maximum number of units of water could be drained by a water pump.
First line contains an integer, T, represent the number of test cases. (1 ≤ T ≤ 20)
For each test case, there are two lines of inputs. For i-th test case,
Answer in T lines. Each line contains an integer to answer each specific test case. Each answer shows the maximum amount of waters can be drained by a water pump.
1 10 3 4 2 3 5 2 1 4 3 2
9
2 2 0 0 10 1 1 2 2 3 3 4 4 5 5
0 5