乌日扬迪亚又发生了一些事情......街上发生了骚乱......著名的乌日扬迪亚超级英雄绵羊谢恩和长颈鹿斯塔斯被召唤来拯救局势。到达后,他们发现市民对主乌日扬迪亚函数 f 的最大值感到担忧,该函数的定义如下:
$$f(l,r)=\sum_{i=l}^{r-1}|a[i]-a[i+1]|\cdot(-1)^{i-l}$$
在上式中,1 ≤ l < r ≤ n 必须成立,其中 n 是主 Uzhlyandian 数组 a 的大小,|x|表示x的绝对值。但英雄们在学校跳过了数学课,所以他们向你寻求帮助。帮助他们计算给定数组 a 的 l 和 r 的所有可能值中 f 的最大值。
输入
第一行包含单个整数 n (2 ≤ n ≤ 105) — 数组 a 的大小。
第二行包含 n 个整数 a1, a2, ..., an (-109 ≤ ai ≤ 109) — 数组元素。
输出
打印唯一的整数——f 的最大值。
示例
输入 #1
5 1 4 2 3 1
输出 #1
3
输入 #2
4 1 5 4 7
输出 #2
6
注意
在第一个示例中,在区间 [1, 2] 和 [2, 5] 上达到 f 的最佳值。
在第二种情况下,f 的最大值只能在整个数组上达到。