### Destopia's blog

By Destopia, history, 16 months ago, Given an array of non-positive integers of length $n$ $(1 \leq n \leq 10^5)$ i.e. $a_i \leq 0$. $(-10^9 \leq a_i \leq 0)$ We want to make all elements equal to $0$. We can do the following operation any number of times (possibly zero).

Choose any subarray and increase all its elements by $1$.

What is the minimum number of operations to make all elements equal to $0$?

Input

7

0 -1 -1 -1 0 -2 -1


Output

3 Comments (7)
| Write comment?
 » 16 months ago, # | ← Rev. 7 →   It would be ${\Large\frac{abs(a_1) + abs(a_n) + \sum_{i=2}^{n} abs(a_i - a_{i-1})}{2}.}$
•  » » 16 months ago, # ^ | ← Rev. 2 →   n = 3a = [-2, -10, -2]ans = 10 not 18
•  » » » Yeah true. I updated my formula.Similar problem : Air Cownditioning
•  » » Proof?
•  » » » I think this might help.
 » Traverse from left to right, break array into segments on getting A[i] = 0,solve each segment individually and add them to get final ans. Each segment will be solved as move to min element index in the segment,assign L and R variable as this index,then just increase L to R contigous subarray value to min(A[L-1],A[R+1]) in 1 step and accrodingly change L and R, increasing subarray length.
 » We can show that answer is equal to $\frac{|a_1| + |a_n| + |a_2 - a_1| + |a_3 - a_2| + \dots + |a_n - a_{n - 1}|}{2}$. Try now solve these two problems: USACO, CodeForces