题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 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

提示

样例 1 解释

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

附加样例

1. 该样例满足 $n=20$，奇数位置的物品重量为 $10^{8}$，偶数位置的物品重量为 $10^{9}$。
2. 该样例满足 $n=200, w_{i}=(i \bmod 47)+1$。
3. 该样例满足 $n=5000$，物品的重量是从区间 $\left[1,10^{9}\right]$ 随机选取的。
4. 该样例满足 $n=5\cdot 10^5, w_{i}=\left\lfloor\frac{(i \bmod 200)}{100}\right\rfloor+1$。
5. 该样例满足 $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}$。
6. 该样例满足 $n=5\cdot 10^5$，物品的重量是从区间 $[1,10^{9}]$ 随机选取的。

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