The problem is equivalent to starting from the given sequence and reaching all zeros in the minimum number of decreasing steps.

The main insight is that if we take a number ~x~ to zero using only one decrease, we should also take all other elements equal to ~x~ in the same step, unless there are elements less than ~x~ in between them. For example, take the sequence ~[4\ 6\ 4\ 5\ 4]~. If we take any ~4~ to zero in a single step, we should decrease the segment spanning all of them.

It is also clear that the minimal nonzero element of the sequence should be taken to zero in a single decrease. This gives us a solution for ~n \le 1000~; just keep track of the minimal nonzero value, and always decrease some minimal elements.

We can make this approach fast using a segment tree, but the intended solution is simpler.

Traverse the sequence from left to right. It can be proven that each element contributes ~1~ step to the optimal solution, except those elements for which there is an element of equal value to the left, and there are no smaller elements between them.

We can efficiently find whether each element satisfies the above condition using a monotone stack. We push values to the top of the stack after popping the stack until the new element is not smaller than the old top of the stack. If the top and the new element have equal values, we don't add ~1~ to the solution. The complexity is ~\mathcal O(n)~.