Fewest range increments to build a target array

You start with an array of n zeros. In one move you choose a contiguous range [l, r] and add 1 to every element in it.

Given a non-negative integer array target of length n, implement:

• min_moves(target: List[int]) -> int: the fewest moves that turn the zero array into target.
• (Part 2) optimal_moves(target: List[int]) -> List[Tuple[int, int]]: one list of inclusive ranges (l, r) of exactly that minimum length. Applying the ranges to the zero array must give target.

Constraints: 0 <= n <= 10^5 and 0 <= target[i] <= 10^9. For part 2, you may assume the answer is small enough to output.

Example 1

target = [2, 4, 1, 3]
min_moves -> 6

Two moves cover the whole prefix to height 2. Two more raise index 1 to 4. Index 2 needs only one of the earlier ranges to continue. Index 3 rises by 2 from 1, so it needs two new ranges. Total: 2 + 2 + 2 = 6.

Example 2

target = [3, 0, 3]
min_moves -> 6

The zero in the middle means no range can cross it, so each side needs its own 3 moves.