← 返回题目列表

Codeforces · 1954/E

E. 连锁反应

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

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