Problem Brief

Optimize Context Switching

A team must optimize context switching between processes. There are n segments where a thread is assigned to each segment. The maximum stack size of a thread assigned in the ith segment is denoted by threadSize[i], for all 1 ≤ i ≤ n. For any high-priority process, some stack size of the segments must be increased. A segment is said to be special when threadSize[i - 1] < threadSize[i] > threadSize[i + 1]. The segments at each end cannot be special. The stack sizes must be modified in such a way as to maximize the number of special segments. To do so, choose any segment and increase the stack size by x. More formally,

Choose an index i and an integer x, where 0 ≤ x ≤ 10^18.
Increase the stack size of the ith segment from threadSize[i] to threadSize[i] + x.

Find the minimum total increase in the stack size of the segments.

1Example 1

Input

threadSize = [3, 1, 4, 5, 5, 2]

Output

Explanation

It is optimal to add 2 and 1 to the third and fifth segments, respectively. The final stack sizes of the segments are [3,1,6,5,6,2].

So the answer = 2 + 1 = 3.

It can be seen that with this change, the required configuration is achieved with a maximum possible of 2 special segments. This is the minimum possible total increase in the stack sizes.

2Example 2

Input

threadSize = [3, 2, 1, 2, 3]

Output

Explanation

Since, the segments at the end cannot be special, both the 2nd and 4th segments must be increased by 2. The final stack sizes are [3, 4, 1, 4, 3].

Constraints

Limits and guarantees your solution can rely on.

🍉🍉