問題説明

近所のカフェ「コードビーン」に開店と同時に客N人が一斉に来て、それぞれ飲み物を注文しました。 バリスタは一度に一杯ずつしか作れず、各注文の調理時間(分)が与えられます。 客は自分の飲み物ができるまで待ち、ある客の「待ち時間」は注文が終わって飲み物を受け取るまでの合計時間です。 バリスタが処理順を自由に決められるとき、全員の待ち時間の合計が最小になる順を決め、その最小総待ち時間を求めてください。

入力

出力

制約条件

• •1 ≤ N ≤ 100,000
• •1 ≤ 各調理時間 ≤ 1,000
• •バリスタは同時に一杯しか作れない (単一処理)
• •全員が開店時刻(0分)に同時に注文する

例

5
3 1 4 1 5

31

3
2 2 2

12