嗷呜嗷呜事务所III

题目描述

在带领完 $n$ 只奇美拉完成了若干任务后，Orange带领的 风堇亲卫队 成功取得了排行榜的第一名。

为了庆祝这一成果，风堇小姐决定亲自奖励这些小奇美拉，为他们治愈疲惫的身体(awsl)。其中，第 $i$ 只奇美拉接受疗愈的时间为 $a_i$。

当然，为了不让所有奇美拉排队等太久，Orange决定让这些小奇美拉们排成一队，使得所有奇美拉的排队等待时间之和最小。

当然，其中有一只小奇美拉非常叛逆，打算拒绝风堇小姐的疗愈，但Orange并不知道它是哪一只。因此，Orange想要计算出假如第 $i$ 只(在原始顺序上)奇美拉不参与排队，那么所有奇美拉的排队等待时间之和最小为多少？

输入格式

输入第一行，为一个整数 $n$，表示奇美拉的数量。 第二行为 $n$ 个整数 $a_i$，表示第 $i$ 只奇美拉需要被疗愈的时间。

数据范围

$1 \le n \le 10^5$ $1\le a_i \le 10^9$

输出格式

输出 $i$ 行，每行一个整数，表示第 $i$ 只奇美拉不参与排队，所有奇美拉最小的等待时间之和。

样例 #1

样例输入 #1

4
1 4 5 1

样例输出 #1

6
3
3
6

提示

样例解释

若第一只奇美拉不参与排队，剩下的奇美拉可以按照 $[a_4,a_2,a_3]$ 的顺序排队，每只奇美拉的等待时间分别为 $0 + 1 + 5 = 6$。可以证明这是一种最优的方案。

若第二只奇美拉不参与排队，剩下的奇美拉可以按照 $[a_1,a_4,a_3]$ 的顺序排队，每只奇美拉的等待时间分别为 $0 + 1 + 2 = 3$。可以证明这是一种最优的方案。

若第三只奇美拉不参与排队，剩下的奇美拉可以按照 $[a_1,a_4,a_2]$ 的顺序排队，每只奇美拉的等待时间分别为 $0 + 1 + 2 = 3$。可以证明这是一种最优的方案。

若第四只奇美拉不参与排队，剩下的奇美拉可以按照 $[a_1,a_2,a_3]$ 的顺序排队，每只奇美拉的等待时间分别为 $0 + 1 + 5 = 6$。可以证明这是一种最优的方案。