C - 展示会の配置 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は美術館の展示企画を担当しています。今度の展示会では、来場者に強い印象を与えるため、作品の配置を工夫することにしました。

展示会には N 個の美術作品があり、それぞれ 1 から N までの番号が付けられています。各作品 i には「色調値」 A_i が設定されており、これは作品の色合いの明るさを数値化したものです。

高橋君は、作品を一列に並べて展示する予定です。来場者へのインパクトを最大化するため、隣り合う作品同士の色調値の差が大きいほど、コントラストが際立って印象的な展示になると考えています。

具体的には、 N 個の作品を一列に並べたとき、隣り合う作品の色調値の差の絶対値をすべて足し合わせた値を「インパクト値」と定義します。すなわち、 1 番目から N - 1 番目までの各位置について、その位置の作品と次の位置の作品の色調値の差の絶対値を計算し、それらの総和がインパクト値となります。

高橋君のために、インパクト値が最大となるように作品を並べたときの、最大のインパクト値を求めてください。

制約

  • 1 \leq N \leq 10^6
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、作品の数を表す整数 N が与えられる。
  • 2 行目には、各作品の色調値を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

インパクト値の最大値を 1 行で出力せよ。

入力例 1

4
1 3 8 10

出力例 1

23

入力例 2

5
7 7 7 7 7

出力例 2

0

入力例 3

10
12 45 3 89 34 21 76 55 8 100

出力例 3

563

入力例 4

30
42 1000000000 17 500000000 999999937 123456789 987654321 314159265 271828182 1 750000000 250000000 600000001 399999999 888888888 111111111 222222222 777777777 333333333 666666666 444444444 555555555 135791357 246802468 975318642 864209753 1024 2048 4096 8192

出力例 4

18117750936

入力例 5

1
1000000000

出力例 5

0

Score : 366 pts

Problem Statement

Takahashi is in charge of planning exhibitions at an art museum. For the upcoming exhibition, he has decided to arrange the artworks strategically to leave a strong impression on visitors.

The exhibition has N artworks, each numbered from 1 to N. Each artwork i has a "tone value" A_i, which is a numerical representation of the brightness of the artwork's color tone.

Takahashi plans to display the artworks in a single row. To maximize the impact on visitors, he believes that the greater the difference in tone values between adjacent artworks, the more the contrast stands out, creating a more impressive exhibition.

Specifically, when the N artworks are arranged in a row, the "impact value" is defined as the sum of the absolute differences in tone values between all pairs of adjacent artworks. That is, for each position from the 1-st to the (N-1)-th, calculate the absolute difference in tone values between the artwork at that position and the artwork at the next position, and the total sum of these values is the impact value.

For Takahashi's sake, find the maximum impact value when the artworks are arranged to maximize the impact value.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq A_i \leq 10^9
  • All inputs are integers

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N representing the number of artworks.
  • The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the tone values of each artwork.

Output

Output the maximum impact value in a single line.

Sample Input 1

4
1 3 8 10

Sample Output 1

23

Sample Input 2

5
7 7 7 7 7

Sample Output 2

0

Sample Input 3

10
12 45 3 89 34 21 76 55 8 100

Sample Output 3

563

Sample Input 4

30
42 1000000000 17 500000000 999999937 123456789 987654321 314159265 271828182 1 750000000 250000000 600000001 399999999 888888888 111111111 222222222 777777777 333333333 666666666 444444444 555555555 135791357 246802468 975318642 864209753 1024 2048 4096 8192

Sample Output 4

18117750936

Sample Input 5

1
1000000000

Sample Output 5

0