← 返回题目列表

Codeforces · 1392/F

F. 奥姆卡和山体滑坡

中文机器翻译题面 查看原题

Omkar 站在 Celeste 山脚下。山顶距离他 $$$n$$$ 米,并且他可以看到到达山顶的所有山脉,因此对于所有 $$$1 \leq j \leq n$$$,他知道距自己 $$$j$$$ 米处的山高为 $$$h_j$$$ 米。事实证明,对于所有满足 $$$1 \leq j \leq n - 1$$$ 的 $$$j$$$,$$$h_j < h_{j + 1}$$$ (意味着高度严格增加)。

突然发生山体滑坡!滑坡发生时,会发生以下情况:每分钟,如果$$$h_j + 2 \leq h_{j + 1}$$$,则一平方​​米的泥土将从$$$j + 1$$$位置滑落到$$$j$$$位置,使得$$$h_{j + 1}$$$减少$$$1$$$,$$$h_j$$$增加$$$1$$$。这些变化同时发生,例如,如果 $$$h_j + 2 \leq h_{j + 1}$$$ 和 $$$h_{j + 1} + 2 \leq h_{j + 2}$$$ 对于某些 $$$j$$$,则 $$$h_j$$$ 将增加 $$$1$$$,$$$h_{j + 2}$$$ 将减少$$$1$$$ 和 $$$h_{j + 1}$$$ 都会增加和减少 $$$1$$$,这意味着实际上 $$$h_{j + 1}$$$ 在该分钟内保持不变。

当不存在 $$$j$$$ 使得 $$$h_j + 2 \leq h_{j + 1}$$$ 时,滑坡结束。帮助 Omkar 算出滑坡结束后 $$$h_1、\dots、h_n$$$ 的值将是多少。可以证明,在给定的约束下,滑坡总是会在有限的分钟内结束。

请注意,由于输入量较大,建议您的代码使用快速 IO。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^6$$$)。

第二行包含 $$$n$$$ 整数 $$$h_1, h_2, \dots, h_n$$$ 满足 $$$0 \leq h_1 < h_2 < \dots < h_n \leq 10^{12}$$$ — 高度。

输出

输出$$$n$$$个整数,其中第$$$j$$$个整数是滑坡停止后$$$h_j$$$的值。

示例

输入 #1

4
2 6 7 8

输出 #1

5 5 6 7

注意

最初,山的高度为 $$$2, 6, 7, 8$$$。

在第一分钟,我们有 $$$2 + 2 \leq 6$$$,因此 $$$2$$$ 增加到 $$$3$$$,$$$6$$$ 减少到 $$$5$$$,留下 $$$3, 5, 7, 8$$$。

在第二分钟,我们有 $$$3 + 2 \leq 5$$$ 和 $$$5 + 2 \leq 7$$$,因此 $$$3$$$ 增加到 $$$4$$$,$$$5$$$ 不变,$$$7$$$ 减少到 $$$6$$$,留下 $$$4, 5, 6, 8$$$。

在第三分钟,我们有 $$$6 + 2 \leq 8$$$,因此 $$$6$$$ 增加到 $$$7$$$,$$$8$$$ 减少到 $$$7$$$,留下 $$$4, 5, 7, 7$$$。

在第四分钟,我们有 $$$5 + 2 \leq 7$$$,因此 $$$5$$$ 增加到 $$$6$$$,$$$7$$$ 减少到 $$$6$$$,留下 $$$4, 6, 6, 7$$$。

在第五分钟,我们有 $$$4 + 2 \leq 6$$$,因此 $$$4$$$ 增加到 $$$5$$$,$$$6$$$ 减少到 $$$5$$$,剩下 $$$5, 5, 6, 7$$$。

在第六分钟,没有什么可以改变,所以山体滑坡停止了,我们的答案是 $$$5, 5, 6, 7$$$。