/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は化学実験を行うことになりました。
この実験では N 個の試薬をすべて、それぞれちょうど1回ずつ処理する必要があります。試薬 i (1 \leq i \leq N) の処理温度は 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}|$$
です。ここで、第1項は開始時の 0 度から最初の試薬の処理温度への変更コスト、最終項は最後の試薬の処理温度から 0 度に戻すコストに対応します。
高橋君は、試薬を処理する順番を最適に選ぶことで、エネルギー消費量の合計を最小化したいと考えています。エネルギー消費量の合計の最小値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq H_i \leq 10^9
- 入力はすべて整数
入力
N H_1 H_2 \cdots H_N
- 1 行目には、試薬の個数を表す整数 N が与えられる。
- 2 行目には、各試薬の処理温度を表す N 個の整数 H_1, H_2, \ldots, H_N がスペース区切りで与えられる。
出力
エネルギー消費量の合計の最小値を整数として 1 行で出力してください。
入力例 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
Score : 300 pts
Problem Statement
Takahashi is going to conduct a chemistry experiment.
In this experiment, he needs to process all N reagents, each exactly once. The processing temperature of reagent i (1 \leq i \leq N) is H_i degrees.
The temperature of the experimental apparatus is initially set to 0 degrees. To process a reagent, the apparatus temperature must be set to exactly match the processing temperature of that reagent. Takahashi can freely choose the order in which to process the reagents. After processing all reagents, he must return the apparatus temperature to 0 degrees to finish the experiment.
When changing the apparatus temperature from a degrees to b degrees, the energy consumption is |a - b|.
If the order of processing the reagents is (p_1, p_2, \ldots, p_N) (a permutation of (1, 2, \ldots, N)), the total energy consumption is
$$|H_{p_1}| + |H_{p_2} - H_{p_1}| + \cdots + |H_{p_N} - H_{p_{N-1}}| + |H_{p_N}|$$
Here, the first term corresponds to the cost of changing from the initial 0 degrees to the processing temperature of the first reagent, and the last term corresponds to the cost of returning from the processing temperature of the last reagent to 0 degrees.
Takahashi wants to minimize the total energy consumption by optimally choosing the order in which to process the reagents. Find the minimum total energy consumption.
Constraints
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq H_i \leq 10^9
- All inputs are integers
Input
N H_1 H_2 \cdots H_N
- The first line contains an integer N, representing the number of reagents.
- The second line contains N integers H_1, H_2, \ldots, H_N separated by spaces, representing the processing temperature of each reagent.
Output
Output the minimum total energy consumption as an integer on a single line.
Sample Input 1
3 5 -3 2
Sample Output 1
16
Sample Input 2
5 10 -5 3 -8 7
Sample Output 2
36
Sample Input 3
8 100 -200 50 -150 300 -50 200 -100
Sample Output 3
1000