P12912 [POI 2020/2021 R2] 收拾背包 / Pakowanie plecaka

翻译来自于 [LibreOJ](https://loj.ac/p/4829)。

**题目译自 [XXVIII Olimpiada Informatyczna – II etap](https://sio2.mimuw.edu.pl/c/oi28-2/dashboard/) [Pakowanie plecaka](https://szkopul.edu.pl/problemset/problem/tFYVKjavLmyczkxMH7WFewXe/statement/)** 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 解释** 输出的第二个数是 $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}]$ 随机选取的。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $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$ |