题目描述

题目译自 XXVIII Olimpiada Informatyczna – II etap Pakowanie plecaka

Bajtazar 准备骑自行车去 Bajtocji 旅游。他现在在考虑要带什么有用的东西在背包里。可惜的是，他没有多少时间，所以他把可能需要的装备按照重要性从高到低排列了一下。他的做法很简单：按顺序检查每个物品，只要不超过背包的承重（当然，要算上之前放进去的物品），就带上它。

还有一个关键的问题：要带什么样的背包呢？Bajtazar 觉得只要带上至少 $k$ 个物品，他就能在旅途中应付得来。可是他还不确定 $k$ 到底是多少。那么，他的背包的承重至少应该是多少，才能保证他带上至少 $k$ 个物品呢？

输入格式

输入的第一行包含一个整数 $n$ $(1 \leq n \leq 5\cdot 10^5)$，表示 Bajtazar 考虑带上的物品的数量。输入的第二行包含 $n$ 个用空格分隔的整数 $w_{1}, w_{2}, \ldots, w_{n}$ $(1 \leq w_{i} \leq 10^{9})$，表示物品的重量，按照 Bajtazar 检查的顺序排列。

输出格式

输出一行 $n$ 个用空格分隔的整数，第 $k$ 个数表示能保证 Bajtazar 带上至少 $k$ 个物品时背包的最小承重。

样例 1

输入

6  
10 8 3 30 5 10

输出

3 13 21 26 36 66

输出的第二个数是 $13$。如果背包的承重是 $13$，那么 Bajtazar 会带上第一个物品（重量为 $10$），不会带上第二个物品（因为他只剩下 $3$ 的承重，而物品重量为 $8$），然后会带上重量为 $3$ 的物品。总共他会带上正好需要的两个物品。

样例 2

见附加文件下 ple1.in 和 ple1.out。

该样例满足 $n=20$，奇数位置的物品重量为 $10^{8}$，偶数位置的物品重量为 $10^{9}$。

样例 3

见附加文件下 ple2.in 和 ple2.out。

该样例满足 $n=200$, $w_{i}=(i \bmod 47)+1$。

样例 4

见附加文件下 ple3.in 和 ple3.out。

该样例满足 $n=5000$，物品的重量是从区间 $\left[1,10^{9}\right]$ 随机选取的。

样例 5

见附加文件下 ple4.in 和 ple4.out。

该样例满足 $n=5\cdot 10^5$, $w_{i}=\left\lfloor\frac{(i \bmod 200)}{100}\right\rfloor+1$。

样例 6

见附加文件下 ple5.in 和 ple5.out。

该样例满足 $n=5\cdot 10^5$, $w_{i}=\left(F_{i} \bmod 100\right)+1$，其中 $F_{0}=0$, $F_{1}=1$, $F_{i+2}=F_{i}+F_{i+1}$。

样例 7

见附加文件下 ple6.in 和 ple6.out。

该样例满足 $n=5\cdot 10^5$，物品的重量是从区间 $[1,10^{9}]$ 随机选取的。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
1	$n \leq 20$	8
2	$n \leq 200$	10
3	$n \leq 5000$	20
4	$w_{i} \leq 2$	8
5	$w_{i} \leq 100$	20
6	无附加限制	34