Bajtazar 正在准备一次环绕拜特城的自行车观光旅行。他现在正在考虑应该带哪些有用的物品放入背包。遗憾的是，他的时间非常紧迫，因此他将所有潜在的装备按重要性从高到低排列成了一个序列。他采取的策略非常简单：按顺序检查每一件物品，只要背包的剩余承重允许（当然，要计入之前已经放入的物品），他就会把这件物品带上。

现在有一个关键问题需要解决：他应该带多大的背包去旅行？Bajtazar 怀疑，只要他能带上至少 $k$ 件物品，他就能应付这次旅行。遗憾的是，我们的主人公还不确定参数 $k$ 具体是多少。在这种情况下，根据参数 $k$，他的背包至少需要多大的承重？

输入格式

输入的第一行包含一个自然数 $n$ ($1 \le n \le 500\,000$)，表示 Bajtazar 考虑携带的潜在物品数量。第二行包含一个由 $n$ 个自然数组成的序列 $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 10^9$)，用空格分隔。这些是物品按 Bajtazar 考虑顺序排列的质量。

输出格式

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

样例

样例输入 1

6
10 8 3 30 5 10

样例输出 1

3 13 21 26 36 66

说明

样例解释：输出的第二个数字是 13。如果背包承重为 13，Bajtazar 将带上第一件物品（质量为 10），不带第二件物品（因为剩余承重仅为 3，而物品质量为 8），并带上第三件物品（质量为 3）。因此，他总共带上了恰好要求的两件物品。

子任务