[R4D]排队问题 - 代码源竞赛平台

时空限制

1S/512M

题目描述

有 $n$ 个学生找老师问问题，老师回答第 $i$ 个学生的问题要花 $a_i$ 分钟。

因为只有一个老师，所以学生们需要排队，定义一名学生的等待时间为老师回答完所有排在他前面的学生的问题所需的总时间。

今天老师只能回答 $n-1$ 名同学的问题，请你对于 $i=1,2,\dots,n$ ，分别求出如果第 $i$ 名同学今天不问问题了，剩下同学等待时间的总和最少是多少。

格式

输入格式

第一行包含一个整数 $n$，表示学生的数量。

第二行包含 $n$ 个整数 $a_i$，分别表示老师回答每个同学问题所需的时间。

输出格式

输出 $n$ 行，每行一个整数表示除了第 $i$ 名同学，剩下同学等待时间的总和的最小值。

样例

样例输入 #1

4
1 4 5 1

样例输出 #1

6
3
3
6

样例解释 #1

除了第 $1$ 名同学，剩下同学按 $\{4,2,3\}$ 排队时等待时间总和最小，为 $(0)+(1)+(1+4)=6$；

除了第 $2$ 名同学，剩下同学按 $\{1,4,3\}$ 排队时等待时间总和最小，为 $(0)+(1)+(1+1)=3$；

除了第 $3$ 名同学，剩下同学按 $\{1,4,2\}$ 排队时等待时间总和最小，为 $(0)+(1)+(1+1)=3$；

除了第 $4$ 名同学，剩下同学按 $\{1,2,3\}$ 排队时等待时间总和最小，为 $(0)+(1)+(1+4)=6$。

数据规模

对于 $100\%$ 的数据， $1\leq n\leq 10^5$， $1\leq a_i\leq 10^9$。

测试点编号	$n$	$a_i$
1~2	$\leq 10$	$\leq 10^9$
3~4	$\leq 1000$
5~6	$\leq 10^5$	$\leq 10^6$
7~10		$\leq 10^9$