CF788A.Functions again

Something happened in Uzhlyandia again... There are riots on the streets... Famous Uzhlyandian superheroes Shean the Sheep and Stas the Giraffe were called in order to save the situation. Upon the arriving, they found that citizens are worried about maximum values of the Main Uzhlyandian Function f, which is defined as follows:

In the above formula, 1 ≤ l < r ≤ n must hold, where n is the size of the Main Uzhlyandian Array a, and |x| means absolute value of x. But the heroes skipped their math lessons in school, so they asked you for help. Help them calculate the maximum value of f among all possible values of l and r for the given array a.

乌兹兰迪亚又发生了一些事情……街头爆发了骚乱……著名的乌兹兰迪亚超级英雄——绵羊谢安（Shean the Sheep）和长颈鹿斯塔斯（Stas the Giraffe）被紧急召来平息局势。抵达现场后，他们发现市民们正为“乌兹兰迪亚主函数”$ f $ 的最大值而担忧，该函数定义如下：

在上述公式中，必须满足 $ 1 \leq l < r \leq n $，其中 $ n $ 是“乌兹兰迪亚主数组”$ a $ 的长度，而 $ |x| $ 表示 $ x $ 的绝对值。但由于两位英雄在学校时逃掉了数学课，因此他们向你求助。请你帮助他们计算：对于给定的数组 $ a $，在所有满足条件的 $ l $ 和 $ r $ 取值下，函数 $ f $ 的最大值是多少？

The first line contains single integer n (2 ≤ n ≤ 105) — the size of the array a.

The second line contains n integers _a_1, _a_2, ..., a__n (-109 ≤ a__i ≤ 109) — the array elements.

第一行包含一个整数 $n$（$2 \leq n \leq 10^5$）——数组 $a$ 的大小。

第二行包含 $n$ 个整数 $a_1,\,a_2,\,\dots,\,a_n$（$-10^9 \leq a_i \leq 10^9$）——数组的元素。

Print the only integer — the maximum value of f.

输出唯一的整数——即 $ f $ 的最大值。

In the first sample case, the optimal value of f is reached on intervals [1, 2] and [2, 5].

In the second case maximal value of f is reachable only on the whole array.

在第一个样例中，函数 $f$ 的最优值在区间 $[1, 2]$ 和 $[2, 5]$ 上取得。

在第二个样例中，函数 $f$ 的最大值仅在整个数组上可达。