問題文

長さ N の数列 A = \left( a_1, a_2, \ldots, a_N \right) が与えられます。

この数列を、いくつかの連続する空でない部分列 B_1, B_2, \ldots, B_K に分割することを考えます。たとえば、A = (5, -3, 6, 2, 4) のとき、A の分割の例は以下のとおりです。

• B_1 = (5), B_2 = (-3, 6, 2), B_3 = (4)
• B_1 = (5, -3), B_2 = (6, 2, 4)
• B_1 = (5, -3, 6, 2, 4)

部分列 B_i の スコア S \left( B_i \right) を、B_i に含まれる項の最大値と最小値の差 \max B_i - \min B_i と定義します。

A を最適に分割したときの、部分列のスコアの和 \sum_i S \left( B_i \right) の最大値を求めてください。

制約

• 入力はすべて整数で与えられる
• 1 \leq N \leq 200{,}000
• |a_i| \leq 10^{9} (1 \leq i \leq N)

入力例 1

9
1 2 2 4 5 2 3 4 1

出力例 1

9

B_1 = (1, 2, 2, 4), B_2 = (5, 2, 3), B_3 = (4, 1) が最適な分割のうちのひとつです。

• S(B_1) = 4 - 1 = 3
• S(B_2) = 5 - 2 = 3
• S(B_3) = 4 - 1 = 3

であるので、その合計である 9 が答えです。

入力例 2

12
3 -1 4 1 5 -9 2 6 5 -3 5 9

出力例 2

37