配点 : $400$ 点

問題文

整数が $N$ 個与えられます。$i$ 個目の整数は $A_i$ です。 これらを好きな順に一列に並べるとき、隣り合う要素の差の合計の最大値を求めてください。

制約

• $2 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$
• 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$

$:$

$A_N$

出力

与えられた整数たちを好きな順に一列に並べるとき、隣り合う要素の差の合計の最大値を出力せよ。

5
6
8
1
2
3

21

$3,8,1,6,2$ の順に並べたとき、隣り合う要素の差の合計は $21$ になり、 これが達成できる最大の値です。

6
3
1
4
1
5
9

25

3
5
5
1

8