G - Dance of Differences
Benihuki
2
s
1024
MB
450
点
問題文
$N$要素からなる数列$A$に対し、スコア$S$を隣接する要素の差の絶対値の和、すなわち以下のように定めます。
$S=\sum_{i=1}^{N-1}|A_{i+1} - A_i|$
$N$要素からなる数列$A$が与えられます。この数列を自由に並び替えることで、得られるスコアの最大値を求めてください。
制約
- $2 \le N \le 2 \times 10^5$
- $1 \le A_i \le 10^9$
入力
$N$
$A_1$ $A_2$ $\cdots$ $A_N$
出力
答えを1行に出力してください。末尾に改行を入れてください。
入力例 1
4
4 1 2 7
出力例 1
14
2 7 1 4のように並べると$|2 - 7| + |7 - 1| + |1 - 4| = 5 + 6 + 3 = 14$となり、これが最大です。
入力例 2
5
1 1 1 1 1
出力例 2
0
入力例 3
6
1 1 1 1 1000000000 1000000000
出力例 3
3999999996
答えは符号付き32bit整数型で表せないこともあります。