序列归零

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　给定一个整数序列：\(d_1, d_2,…,d_N\)，每个整数都在 \(−10^{15}\) 与 \(10^{15}\) 之间，\(N\) 不超过 \(2⋅10^5\)。可以用下面两种操作来对序列进行变换：

　　●操作1、设定一个 \(1\) 到 \(N\) 之间的整数 \(L\)，然后就可以把 \(d_N\) 增加 \(L\)，\(d_{N-1}\) 增加 \(L-1\)，\(d_{N-2}\) 增加 \(L-2\) …以此类推。\(d_1\) 到 \(d_{N-L}\) 将不会有任何变化；
　　●操作2、设定一个 \(1\) 到 \(N\) 之间的整数 \(L\)，可以把 \(d_N\) 减少 \(L\)，\(d_{N-1}\) 减少 \(L-1\)，\(d_{N-2}\) 减少 \(L-2\) …，以此类推。\(d_1\) 到 \(d_{N-L}\) 将不会有任何变化。

　　请问最少要进行多少次操作才能把序列全部变成0？

【输入格式】

　　输入的第一行包含 \(N\)。
　　第二行包含 \(N\) 个整数 \(d_1…d_N\) ，表示初始序列。

【输出格式】

　　输出一个整数，表示做少的操作次数。输入保证答案不超过 \(10^9\)。

【输入输出样例1】

　Input

2
-1 3

　Output

6

【样例1解释】

　　先连续进行五次操作2，设定L=1，序列变成：-1, -2；
　　再进行一次操作1，设定L=2，序列变成：0, 0；

【输入输出样例2】

　Input

5
1 3 -2 -7 5

　Output

26

【样例2解释】

　　先进行 7 次操作1：设定 \(L=3\)，则序列变为：1 3 5 7 26
　　再进行 17 次操作2：设定 \(L=1\)，则序列变为：1 3 5 7 9
　　再进行 1 次操作2：设定 \(L=5\)，则序列变为：0 1 2 3 4
　　再进行 1 次操作2：设定 \(L=4\)，则序列变为：0 0 0 0 0。
　　共进行了 17+7+1+1=26 次操作。

【测试点性质】

　　测试点 \(1−5：N≤10^3\)，答案不超过 \(10^3\) 。
　　测试点 \(6−10：N≤10^3\) 。
　　测试点 \(11−15：\)没有额外限制。

【来源】

　　Mr.he