問題文
鳗鱼在圣诞节从圣诞兔那里得到数列 A=\{A_1,A_2,...,A_N\} 。
鳗鱼是数列 A 中的几个(0 个也可以)的元素被删除,制作了“良好数列”。数列 x 是良好数列是指满足以下性质。
- 全部 i (2 ≦ i ≦ |x|-1) , 当我输入x_i 是 您也可以写 x_{i-1}, x_i, x_{i+1} 中的不是中位数。
例如 第 x=\{2,1,3,2\} 呀 请注意,它可能是 x=\{2,1,2\} 满足条件,但是x=\{1,2,3\} 呀 请注意,它可能是 x=\{1,1,3,2\} 不满足条件。 另外,长度小于 3 的数列也满足条件。
数列 x 的凹凸度定义为相邻数字之差的和。用数学式表示凹凸度为Σ_{1 ≦ i ≦ |x|-1} |x_i - x_{i+1}| 。 对于
这时,请求可以制作的良好数列的凹凸度最大值。
入力
输入是按以下格式从标准输入给出的。
N A_1 A_2 ... A_N
- 1 编号顺序是 第一个 A 长度的整数 N (2≦N≦10^5) 。 表示
- 2 行中,N 整数由空格分隔。其中 i (1 ≦ i ≦ N) 第几个为整数 A_i (0 ≦ A_i ≦ 10^9) 。 表示
部分点
针对此问题设置了部分分数。
- N≦1,000 的数据集,20 点。 如果您正确回答了所有满足
- 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 80 点。 如果您正确回答了所有满足
出力
数列 A 通过删除一些元素得到的良好数列中的凹凸度最大值输出。 输出末尾加换行符。
入力例 1
5 1 1 3 2 1
出力例 1
4
例如,1,4 删除第几个元素后 \{1,3,1\} 变为,并且凹凸值为 4 。 对于
入力例 2
7 2 1000000000 0 1000000000 1 1000000000 5
出力例 2
5999999991