分数: 300 分
问题陈述
高桥要进行化学实验。
在这个实验中,他需要处理所有 N 试剂,每个恰好一次。试剂处理温度 i (1 \leq i \leq N) is H_i 度。
实验装置的温度初始设置为 0 度。为了处理试剂,必须将设备温度设置为与该试剂的处理温度完全匹配。高桥可以自由选择处理试剂的顺序。处理完所有试剂后,他必须将仪器温度恢复到 0 度完成实验。
将设备温度从 a 度至 b 度,能耗为 |a - b|.
如果处理试剂的顺序是 (p_1, p_2, \ldots, p_N) (排列 (1, 2, \ldots, N)),总能耗为
$$|H_{p_1}| + |H_{p_2} - H_{p_1}| + \cdots + |H_{p_N} - H_{p_{N-1}}| + |H_{p_N}|$$
这里,第一项对应于从初始状态改变的成本 0 度为第一个试剂的处理温度,最后一项对应于从最后一个试剂的处理温度返回到 0 度。
Takahashi 希望通过优化选择试剂处理顺序来最大限度地减少总能耗。求最小总能耗。
约束
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq H_i \leq 10^9
- 所有输入均为整数
输入
N H_1 H_2 \cdots H_N
- 第一行包含一个整数 N,代表试剂数量。
- 第二行包含 N 整数 H_1, H_2, \ldots, H_N 以空格分隔,代表每种试剂的处理温度。
输出
在单行上以整数形式输出最小总能耗。
示例输入 1
3 5 -3 2
示例输出 1
16
示例输入 2
5 10 -5 3 -8 7
示例输出 2
36
示例输入 3
8 100 -200 50 -150 300 -50 200 -100
示例输出 3
1000