Editorial for Mock CCC '18 Contest 2 J3/S1 - An Array Problem
Submitting an official solution before solving the problem yourself is a bannable offence.
The answer is:
The left expression is an upper bound on the answer because if we consider the smallest elements, each operation has to decrease at least one of those entries.
The right expression is an upper bound on the answer since the sum of the list decreases by per operation and cannot be negative.
If the left expression bounds the answer, then the optimal arrangement is to always decrease the maximal element once and force the other elements to zero.
If the right expression bounds the answer, we can simultaneously decrease the smallest and largest element and repeat this until the list contains at most one .