Subtask 1

Let ~[S_1, \dots, S_k]~ be non-decreasing and let ~[S_{k+1}, \dots, S_N]~ be non-increasing.

For ~S_i~ to be non-decreasing, we want ~S_i \le S_{i+1}~. Thus we must add ~\max(0, S_i - S_{i+1})~ to ~S_{i+1}~.

Similarly, for ~S_i~ to be non-increasing, we want ~S_i \ge S_{i+1}~. Thus we must add ~\max(0, S_{i+1} - S_i)~ to ~S_i~.

Finally, either ~S_k \le S_{k+1}~ or ~S_k \ge S_{k+1}~, so we are done.

Doing this by iterating the array for each value of ~k~ gives an ~\mathcal O(N^2)~ solution.

Time Complexity: ~\mathcal O(N^2)~

Subtask 2

Note that if ~[S_1, \dots, S_k]~ is non-decreasing, then ~[S_1, \dots, S_{k-1}]~ must also be non-decreasing. Thus we can precompute the amount of time it takes ~[S_1, \dots, S_k]~ to become non-decreasing for all ~k~ in ~\mathcal O(N)~.

By the same argument, we can precompute the amount of time it takes ~[S_k, \dots, S_N]~ to become non-increasing for all ~k~ in ~\mathcal O(N)~.

Iterating the array for each value of ~k~ again, we obtain an ~\mathcal O(N)~ solution.

Time Complexity: ~\mathcal O(N)~

Alternate Solution

We present a greedy algorithm that solves the problem in ~\mathcal O(N)~. We take advantage of the fact that it is never optimal to increment ~a_k~ if ~a_k = \max(S)~.

1. Find an index ~i~ such that ~S_i = \max (S)~.
2. Now make ~[S_1, \dots, S_i]~ non-decreasing and make ~[S_i, \dots, S_N]~ non-increasing.

Note that both steps take ~\mathcal O(N)~ time and thus the overall algorithm also takes ~\mathcal O(N)~ time.

Time Complexity: ~\mathcal O(N)~