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$$$。