题目描述

题目译自 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$ 个物品时背包的最小承重。

6
10 8 3 30 5 10

3 13 21 26 36 66

样例 2

见附加文件下 [ple1.in](file:ple1.in) 和 [ple1.out](file:ple1.out)。

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

样例 3

见附加文件下 [ple2.in](file:ple2.in) 和 [ple2.out](file:ple2.out)。

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

样例 4

见附加文件下 [ple3.in](file:ple3.in) 和 [ple3.out](file:ple3.out)。

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

样例 5

见附加文件下 [ple4.in](file:ple4.in) 和 [ple4.out](file:ple4.out)。

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

样例 6

见附加文件下 [ple5.in](file:ple5.in) 和 [ple5.out](file: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](file:ple6.in) 和 [ple6.out](file: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$