E - 展示ブースの配置 解説 /

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

配点 : 433 点

問題文

高橋君は文化祭の実行委員長を務めています。文化祭では N 個の展示ブースが横一列に並んで設置されます。左から順にブース 1 , ブース 2 , ..., ブース N と番号が付けられています。

N 個の出展団体がそれぞれ 1 つずつブースを使用します。各出展団体 i には、展示の派手さを表す値 C_i が定まっています。隣り合うブースに配置された 2 つの出展団体の派手さの差の絶対値が「コントラスト」として計算されます。すなわち、ブース j に出展団体 p が、ブース j+1 に出展団体 q が配置されているとき、その隣り合うペアのコントラストは |C_p - C_q| です。

文化祭全体の「総コントラスト」は、隣り合う全てのペア（ N - 1 組）のコントラストの合計です。

高橋君は、来場者が歩きながら変化に富んだ展示を楽しめるよう、総コントラストをできるだけ大きくしたいと考えています。高橋君は N 個の出展団体のブースへの配置を自由に決めることができます。

総コントラストを最大化するとき、その最大値を求めてください。

制約

  • 2 \leq N \leq 10^6
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数である。

入力

N
C_1 C_2 \ldots C_N
  • 1 行目には、出展団体の数を表す整数 N が与えられる。
  • 2 行目には、各出展団体の派手さを表す N 個の整数 C_1, C_2, \ldots, C_N がスペース区切りで与えられる。

出力

総コントラストの最大値を 1 行で出力せよ。

入力例 1

4
1 3 8 10

出力例 1

23

入力例 2

5
5 5 5 5 5

出力例 2

0

入力例 3

12
4 15 15 8 23 42 16 9 31 7 7 50

出力例 3

254

入力例 4

30
1000000000 1 500000000 250000000 750000000 123456789 987654321 333333333 666666666 42 999999999 314159265 271828182 161803398 141421356 173205080 223606797 707106781 888888888 111111111 222222222 444444444 555555555 777777777 99999999 900000000 800000000 700000000 600000000 400000000

出力例 4

16859449268

入力例 5

2
1 1000000000

出力例 5

999999999

Score : 433 pts

Problem Statement

Takahashi is the chairperson of the school festival committee. At the festival, N exhibition booths will be set up in a horizontal row. The booths are numbered 1, 2, \ldots, N from left to right.

There are N exhibiting groups, and each group will use exactly one booth. Each group i has a value C_i representing the "flashiness" of its exhibition. The absolute difference in flashiness between two groups placed in adjacent booths is defined as the "contrast". Specifically, if group p is placed in booth j and group q is placed in booth j+1, the contrast of this adjacent pair is |C_p - C_q|.

The "total contrast" of the entire festival is the sum of the contrasts of all adjacent pairs (N - 1 pairs).

Takahashi wants to maximize the total contrast so that visitors can enjoy a highly varied sequence of exhibitions as they walk. He can freely decide the assignment of the N groups to the booths.

Find the maximum possible total contrast.

Constraints

  • 2 \leq N \leq 10^6
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
  • All input values are integers.

Input

N
C_1 C_2 \ldots C_N
  • The first line contains an integer N, representing the number of exhibiting groups.
  • The second line contains N space-separated integers C_1, C_2, \ldots, C_N, representing the flashiness of each group.

Output

Print the maximum possible total contrast in a single line.

Sample Input 1

4
1 3 8 10

Sample Output 1

23

Sample Input 2

5
5 5 5 5 5

Sample Output 2

0

Sample Input 3

12
4 15 15 8 23 42 16 9 31 7 7 50

Sample Output 3

254

Sample Input 4

30
1000000000 1 500000000 250000000 750000000 123456789 987654321 333333333 666666666 42 999999999 314159265 271828182 161803398 141421356 173205080 223606797 707106781 888888888 111111111 222222222 444444444 555555555 777777777 99999999 900000000 800000000 700000000 600000000 400000000

Sample Output 4

16859449268

Sample Input 5

2
1 1000000000

Sample Output 5

999999999