Server Time:

User's AC Ratio in this contest

65.2% (15/23)

Submission's AC Ratio in this contest

23.8% (15/63)

Description

相信大家看完上週的影片之後已經很了解跟範圍有關的詢問的問題了,並且也知道如何快速解出來,因此希望你可以幫我寫個程式找出下面的答案。

定義一個函數 $f$:

$$
f(l, r) = \sum_{i = l}^{r - 1}|a_{i + 1} - a_i| \cdot (-1) ^ {i - l} , 1 \leq l < r \leq n
$$

函數中的 $a$ 是一個長度為 $n$ 的陣列,而 $|m|$ 代表對 $m$ 取絕對值。

請你幫我找出將所有可能的 $l, r$ 代入 $f$ 之後會得到的最大值 $x$。
用公式表示就是 $\displaystyle x = \max_{1 \leq l < r \leq n}\left\{ f(l, r) \right\}$。

Input Format

輸入只有 $2$ 行;
第 $1$ 行只有一個整數 $n$,代表陣列長度;
第 $2$ 行有 $n$ 個整數 $a_1, a_2, \dots, a_n$,代表陣列中的元素。

  • $2 \leq n \leq 10^5$
  • $-10^9 \leq a_i \leq 10^9$

Output Format

輸出一個整數 $x$,代表 $\displaystyle \max_{1 \leq l < r \leq n}\left\{ f(l, r) \right\}$。

Sample Input 1

5
1 4 2 3 1

Sample Output 1

3

Sample Input 2

4
1 5 4 7

Sample Output 2

6

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~17 無特別限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1
10 1000 65536 65536 1
11 1000 65536 65536 1
12 1000 65536 65536 1
13 1000 65536 65536 1
14 1000 65536 65536 1
15 1000 65536 65536 1
16 1000 65536 65536 1
17 1000 65536 65536 1