题目描述

现得到了一个数列 $B$，他认为这个数列不够可爱，于是他决定重新创造一个数列 A，规则如下

对于所有的 $i$ ，需要保证 $A_i$ 在 $[1-B_i]$ 这个区间内 现在，我们称数列 A 的可爱值为 「数列 A 中相邻两个数差的绝对值的和」，求最大的可爱值。

输入格式

第一行一个整数 $n$ ，代表数列B的长度

第二行 $n$ 个整数 $B_i$

2<= $n$ <=1e5

1<=$B_i$<=1e4

输出格式

最大的可爱值

8
11 45 14 19 1 9 8 10

149