题意
解
考场上：
首先观察答案是一段连续的区间，然后想到二分，再用类似NOIP2018D1T1的方法验证。时间复杂度可以达到 (O(n+log n)) 。
In fact，这是道差分题。
我们让差分数组 (s[i]=a[i]-a[i-1]) ，实际上就是要把 (s[2..n]) 全变成0。
- 首先一个正数-1、一个负数+1产生的贡献是它们的绝对值的较小值。进行若干次这种操作，会使差分数组中所有的非0元素同号。
- 在剩下的数中，将正数-1、 (s[n+1]) +1产生贡献是正数本身，将 (s[1]) -1、负数+1产生贡献是负数的绝对值。
设所有正数的和为 (x) ，所有负数的和的绝对值为 (y) ，总贡献为 (min(x,y)+|x-y|=max(x,y)) 。第一问解决。
第二问的话，差分数组中所有的非0元素变为同号后有 (|x-y|+1) 种方案。