有$$$n$$$个怪物站成一排。第 $$$i$$$ 个怪物拥有 $$$a_i$$$ 生命值。
每秒,你可以选择一个活着的怪物并向其发射连锁闪电。闪电对其造成 $$$k$$$ 伤害,并且向左(朝向减少 $$$i$$$)和向右(朝向增加 $$$i$$$)传播到活着的怪物,对每个怪物造成 $$$k$$$ 伤害。当闪电到达死去的怪物或行的开头/结尾时,它就会停止。如果怪物的生命值严格大于 $$$0$$$,则怪物被视为活着。
例如,考虑以下场景:存在三个生命值等于 $$$[5, 2, 7]$$$ 的怪物,并且 $$$k = 3$$$。你可以在 $$$4$$$ 秒内杀死他们:
- 对$$$3$$$-rd怪物发射连锁闪电,那么它们的生命值为$$$[2, -1, 4]$$$;
- 对$$$1$$$-st怪物发射连锁闪电,则其生命值为$$$[-1, -1, 4]$$$;
- 对$$$3$$$-rd怪物发射连锁闪电,那么它们的生命值为$$$[-1, -1, 1]$$$;
- 对第$$$3$$$个怪物发射连锁闪电,那么它们的生命值为$$$[-1, -1, -2]$$$。
对于从$$$1$$$到$$$\max(a_1, a_2, \dots, a_n)$$$的每个$$$k$$$,计算杀死所有怪物所需的最小秒数。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 怪物的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — 第 $$$i$$$ 个怪物的生命值。
输出
对于从$$$1$$$到$$$\max(a_1, a_2, \dots, a_n)$$$的每个$$$k$$$,输出杀死所有怪物所需的最小秒数。
示例
输入 #1
3 5 2 7
输出 #1
10 6 4 3 2 2 1
输入 #2
4 7 7 7 7
输出 #2
7 4 3 2 2 2 1
输入 #3
10 1 9 7 6 2 4 7 8 1 3
输出 #3
17 9 5 4 3 3 3 2 1