AT_codequeen2023_final_e Good Partition

長さ $ 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) $ の最大値を求めてください。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ a_1 $ $ a_2 $ $ \ldots $ $ a_N $

部分列のスコアの和の最大値を出力してください。

### Sample Explanation 1 $ 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 $ が答えです。 ### Constraints - 入力はすべて整数で与えられる - $ 1 \leq N \leq 200{,}000 $ - $ |a_i| \leq 10^{9} $ $ (1 \leq i \leq N) $