题目背景

“若这样的话，阁下的实力还不足以踏进那块地方” “七步之外我的斧子快，七步之内，我的斧子更快。” “过了这么多年，森林外的人还是这么弱吗。” “就凭这种程度，还无法踏足那片森林，击败我的那两位旧友，和森林深处的那位王。” “天不生我光头强，锯道万古如长夜！” 您正在老梗新玩，突然，『他』进来了。 您开始做一道网络流题目。

题目描述

强的心愿是守护一方净土，但狗熊岭外险恶的世界却并不会让他安宁。 邪恶的幕府武士军团开始入侵狗熊岭。 “妈，我干完这一票，就回团结屯和您过年。” 电话落地，长刀出鞘...... 强有一个武力值 𝐹，最开始为 0。 他需要击败 𝑛 个武士，第 𝑖 个武士的战力为 𝑎𝑖。 在击杀第 𝑖 个武士时，强的武力值 𝐹 会因此发生改变：

• 若 𝐹 > 𝑎𝑖，强会认为敌人不值得自己认真而收起斧子，减少一点武力值。 • 若 𝐹 = 𝑎𝑖，强会认为敌人势均力敌，战斗状态不改变，即武力值不变。 • 若 𝐹 < 𝑎𝑖，强会认为敌人较强而拿出斧子，增加一点武力值。

当然，再强大的人也需要好的策略。 在强血洗武士军团过程中，你需要实现为他规划好战略，你需要算出对于 ∀𝑖 ∈ [1, 𝑛]，他将前 𝑖 个武士击杀 后，他的武力值最大能够是多少，前 𝑖 个武士的击杀顺序可以任意调换。 如果你帮他正确地规划，他会请你吃自家珍藏的馒头，否则他会请你吃斧子。

输入格式

第一行一个正整数 𝑛，表示强要挑战的武士的个数。 第二行 𝑛 个正整数 𝑎𝑖，表示第 𝑖 个武士的战力。

输出格式

输出 𝑛 行， 第 𝑖 行，表示击败前 𝑖 个武士后最大武力值。

样例 #1

样例输入 #1

6 8 9 7 6 6 1

样例输出 #1 1 2 3 4 5 6

提示

样例一解释

• 对于 𝑘 = 1 ∼ 5，显然按原顺序即可。

• 对于 𝑘 = 6，将 1 放在第一个即可。

注意: 本题采用捆绑测试, 只有当你通过一个子任务中的所有测试点后, 你才能拿到这个子任务的分数。

子任务编号 数据范围 分值 子任务依赖

1 𝑛 ⩽ $10^3$ $10$ 无

2 𝑛 ⩽ $2 × 10^4$ $20$ 1

3 𝑛 ⩽ $10^5$ $30$ $2$

4 𝑛 ⩽ $2 × 10^6$ $40$ $3$

对于 100% 的数据，保证 1 ⩽ 𝑛 ⩽ $2 × 10^6$ , $−2 × 10^6 ⩽ 𝑎𝑖 ⩽ 2 × 10^6$。