A canal has n locks in a single line, and lock i currently holds water level level[i]. For barges to move safely down the canal, the levels must be non-decreasing from the first lock to the last. Maintenance crews can only pump extra water into a lock — never drain one — and each unit of water pumped into any single lock counts as one operation. Find the minimum total number of units that must be pumped in, across all locks, so the sequence of levels becomes non-decreasing.
Line 1: an integer n.
Line 2: n integers, level[0..n-1].
A single integer: the minimum total units of water that must be pumped in.
1 <= n <= 2*10^50 <= level[i] <= 10^9Example 1
Input
4 3 1 4 2
Expected
4
Explanation
The running floor starts at 3. Lock 1 (value 1) is below the floor, so pump in 2 units to raise it to 3 (floor stays 3). Lock 2 (value 4) raises the floor to 4. Lock 3 (value 2) is below the floor, so pump in 2 units to raise it to 4. Total pumped: 2 + 2 = 4.
Example 2
Input
3 2 2 5
Expected
0
Explanation
The levels 2, 2, 5 are already non-decreasing, so no pumping is needed and the answer is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →