Problem Statement

Amazon Web Services lets teams scale their applications horizontally by spinning up a fleet of n servers. For optimal load balancing, the engineering team wants the computational capacities of these servers to be arranged in non-decreasing order . To achieve this, you are allowed to repeatedly pick any contiguous range of servers and uniformly raise their capacity by some positive integer x . You may perform this operation as many times as needed. The objective is to determine the minimum total amount (sum of all chosen x values across operations) that needs to be added so that the final capacity sequence becomes non-decreasing. Example Consider a fleet with n = 5 servers having capacities capacity = [3, 4, 1, 6, 2] . One valid strategy is: add 3 to the contiguous segment (2, 4), and then add 4 to the segment (4, 4). After these operations the fleet becomes [3, 4, 4, 9, 9] , which is non-decreasing. The total boost spent is 3 + 4 = 7, which is the optimum. Function Description Implemen