题解：AT_arc129_d [ARC129D] -1+2-1

很厉害的推式子题，要多训式子了。

下面默认下标为 $0$ 时是 $n$，为 $n+1$ 时是 $1$。

可以先非常典型的设 $x_i$ 表示 $i$ 操作了多少次（$x_i\geq 0$），那么答案就是 $\sum_{i=1}^{n}x_i$。

考察 $x$ 的性质，不难发现有 $2\times x_i-x_{i-1}-x_{i+1}+a_i=0$。

发现上面的式子有个同构，设 $b_i=x_i-x_{i-1}$，有 $b_{i+1}-b_i=a_i$。

接着考察性质，发现本题中 $\sum_{i=1}^{n} a_i$ 如果不等于 $0$ 一定无解，所以我们只要考虑 $\sum_{i=1}^{n}a_i=0$ 的情况。

发现把若干个 $a$ 加起来的结果会产生相消，所以不妨加起来：

再发现 $\sum_{i=1}^{n}b_i$ 是等于 $0$ 的，所以不妨把上面那个式子也加起来：

把 $-nb_1$ 移到右边去就构造出了 $\sum_{i=1}^{n}b_i$，于是有：

解个方程有：

接着我们就可以递推出 $b$ 数组的所有值了。

接着考虑解决 $x$，因为 $x_i=x_{i-1}+b_i$，所以只需要确定 $x_1$ 的最小值即可。

由于我们有 $x_i\geq 0$ 的性质，所以说只要递推一遍，将 $b$ 的前缀和中最小的数的相反数和 $0$ 取 max 即可，具体实现细节可看代码。

总时间复杂度 $\operatorname{O}(n)$。