Good Sequence
题意翻译
给出一个正整数 $n$ 和长度为 $n$ 的序列 $A$ ,求 $A$ 中相邻两数差的和。
题目描述
[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 $ からいくつかの要素を消すことで得られる良い数列のうちのデコボコ度の最大値を出力せよ。 出力の末尾に改行を入れること。
输入输出样例
输入样例 #1
5
1 1 3 2 1
输出样例 #1
4
输入样例 #2
7
2 1000000000 0 1000000000 1 1000000000 5
输出样例 #2
5999999991
说明
### 部分点
この問題には部分点が設定されている。
- $ N≦1,000 $ を満たすデータセットに正解した場合は、$ 20 $ 点が与えられる。
- 追加制約のないデータセットに正解した場合は、上記とは別に $ 80 $ 点が与えられる。
### Sample Explanation 1
例えば、$ 1,4 $ 番目の要素を消すと $ \{1,3,1\} $ となり、デコボコ値は $ 4 $ となります。