CF484D.Kindergarten

In a kindergarten, the children are being divided into groups. The teacher put the children in a line and associated each child with his or her integer charisma value. Each child should go to exactly one group. Each group should be a nonempty segment of consecutive children of a line. A group's sociability is the maximum difference of charisma of two children in the group (in particular, if the group consists of one child, its sociability equals a zero).

The teacher wants to divide the children into some number of groups in such way that the total sociability of the groups is maximum. Help him find this value.

在一家幼儿园中，孩子们需要被分成若干组。老师将孩子们排成一列，并为每个孩子分配一个整数魅力值。每个孩子必须且仅能属于一个组；每个组必须是由该队列中连续的一段（非空）孩子构成。一个组的社交性定义为该组内任意两个孩子魅力值之差的最大值（特别地，若该组仅含一个孩子，则其社交性为 0）。

老师希望将孩子们划分为若干组，使得所有组的社交性之和最大。请帮助他求出这个最大值。

The first line contains integer n — the number of children in the line (1 ≤ n ≤ 106).

The second line contains n integers a__i — the charisma of the i-th child ( - 109 ≤ a__i ≤ 109).

第一行包含一个整数 $n$ —— 队列中儿童的数量（$1 \leq n \leq 10^6$）。

第二行包含 $n$ 个整数 $a_i$ —— 第 $i$ 个儿童的个人魅力值（$-10^9 \leq a_i \leq 10^9$）。

Print the maximum possible total sociability of all groups.

输出所有组的最大可能总社交性。

In the first test sample one of the possible variants of an division is following: the first three children form a group with sociability 2, and the two remaining children form a group with sociability 1.

In the second test sample any division leads to the same result, the sociability will be equal to 0 in each group.

在第一个测试样例中，一种可能的分组方式如下：前三名儿童组成一个亲和度为 2 的小组，其余两名儿童组成一个亲和度为 1 的小组。

在第二个测试样例中，任意分组方式都会得到相同的结果，即每个小组的亲和度均为 0。