Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. Functions again

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputSomething 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*.

Input

The first line contains single integer *n* (2 ≤ *n* ≤ 10^{5}) — the size of the array *a*.

The second line contains *n* integers *a*_{1}, *a*_{2}, ..., *a*_{n} (-10^{9} ≤ *a*_{i} ≤ 10^{9}) — the array elements.

Output

Print the only integer — the maximum value of *f*.

Examples

Input

5

1 4 2 3 1

Output

3

Input

4

1 5 4 7

Output

6

Note

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/23/2018 06:35:37 (f1).

Desktop version, switch to mobile version.

User lists

Name |
---|