AT_xmascontest2015_g Good Sequence

[problemUrl]: https://atcoder.jp/contests/xmascontest2015noon/tasks/xmascontest2015_g うなぎはクリスマスにサンタうさぎから数列 $ 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) $ が与えられる。

数列 $ A $ からいくつかの要素を消すことで得られる良い数列のうちのデコボコ度の最大値を出力せよ。 出力の末尾に改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ N≦1,000 $ を満たすデータセットに正解した場合は、$ 20 $ 点が与えられる。 - 追加制約のないデータセットに正解した場合は、上記とは別に $ 80 $ 点が与えられる。 ### Sample Explanation 1 例えば、$ 1,4 $ 番目の要素を消すと $ \{1,3,1\} $ となり、デコボコ値は $ 4 $ となります。