Things begin with an array filled with N zeros, and, we, as a team, want to obtain an array A.
In one move, we can choose an arbitrary inverval and increase all the elements within that inverval by 1. For example:::
We can transform [0, 0, 0, 0, 0] into [0, 1, 1, 1, 0] in a single move.
BUT! We need three moves to obtain [1, 0, 1, 2, 2]. One possible sequence of moves is: [0, 0, 0, 0 , 0] -> [0, 0, 1, 1, 1] -> [0, 0, 1, 2, 2] -> [1, 0, 1, 2, 2], where -> denotes a single move.
What is the minimum number of moves needed to obtain A? Starting from a zero-filled array?
Given an array A of length N, returns an integer that represents the minimum number of moves needed to transform a zero-filled array into A
Example 1:
Input: A = [2, 1, 3]
Output: 4
Explanation:The following sequence of moves leads to the solution - [0, 0, 0] → [1, 1, 1] → [2, 1, 1] → [2, 1, 2] → [2, 1, 3]
Example 2:
Input: A = [2, 2, 0, 0, 1]
Output: 3
Explanation:The following sequence of moves leads to the solution: [0, 0, 0, 0, 0] → [1, 1, 0, 0, 0] → [2, 2, 0, 0, 0] → [2, 2, 0, 0, 1].
Example 3:
Input: A = [5, 4, 2, 4, 1]
Output: 7
Explanation:One possible optimal sequence of moves is: [0, 0, 0, 0, 0] → [1, 1, 1, 1, 1] → [2, 2, 2, 2, 1] → [3, 3, 2, 2, 1] → [4, 4, 2, 2, 1] → [5, 4, 2, 2, 1] → [5, 4, 2, 3, 1] → [5, 4, 2, 4, 1].
N is an integer within the range [1..100,000]each element of array A is an integer within the range [0..1,000,000,000]we guarantee that the answer will not exceed 1,000,000,000
input:
output: