311239: CF1954E. Chain Reaction

E. Chain Reactiontime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

There are $n$ monsters standing in a row. The $i$-th monster has $a_i$ health points.

Every second, you can choose one alive monster and launch a chain lightning at it. The lightning deals $k$ damage to it, and also spreads to the left (towards decreasing $i$) and to the right (towards increasing $i$) to alive monsters, dealing $k$ damage to each. When the lightning reaches a dead monster or the beginning/end of the row, it stops. A monster is considered alive if its health points are strictly greater than $0$.

For example, consider the following scenario: there are three monsters with health equal to $[5, 2, 7]$, and $k = 3$. You can kill them all in $4$ seconds:

• launch a chain lightning at the $3$-rd monster, then their health values are $[2, -1, 4]$;
• launch a chain lightning at the $1$-st monster, then their health values are $[-1, -1, 4]$;
• launch a chain lightning at the $3$-rd monster, then their health values are $[-1, -1, 1]$;
• launch a chain lightning at the $3$-th monster, then their health values are $[-1, -1, -2]$.

For each $k$ from $1$ to $\max(a_1, a_2, \dots, a_n)$, calculate the minimum number of seconds it takes to kill all the monsters.

Input

The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of monsters.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$) — the health points of the $i$-th monster.

Output

For each $k$ from $1$ to $\max(a_1, a_2, \dots, a_n)$, output the minimum number of seconds it takes to kill all the monsters.

ExamplesInput

3
5 2 7

Output

10 6 4 3 2 2 1 

Input

4
7 7 7 7

Output

7 4 3 2 2 2 1 

Input

10
1 9 7 6 2 4 7 8 1 3

Output

17 9 5 4 3 3 3 2 1 

题目大意：
E. 链式反应

有 $ n $ 个怪物站在一行中，第 $ i $ 个怪物有 $ a_i $ 点生命值。

每秒钟，你可以选择一个**活着的**怪物对其发动链状闪电。闪电对其造成 $ k $ 点伤害，并传播到左边（向减少的 $ i $ 方向）和右边（向增加的 $ i $ 方向）的**活着的**怪物，对每个怪物造成 $ k $ 点伤害。当闪电到达一个死怪物或行首/行尾时，它停止。如果一个怪物的生命值严格大于 $ 0 $，则认为它是活着的。

对于每个 $ k $ 从 $ 1 $ 到 $ \max(a_1, a_2, \dots, a_n) $，计算杀死所有怪物所需的最少秒数。

输入输出数据格式：

输入：
- 第一行包含一个整数 $ n $（$ 1 \le n \le 10^5 $）——怪物的数量。
- 第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $（$ 1 \le a_i \le 10^5 $）——第 $ i $ 个怪物的生命值。

输出：
- 对于每个 $ k $ 从 $ 1 $ 到 $ \max(a_1, a_2, \dots, a_n) $，输出杀死所有怪物所需的最少秒数。

示例输入输出：

输入：
```
3
5 2 7
```
输出：
```
10 6 4 3 2 2 1
```

输入：
```
4
7 7 7 7
```
输出：
```
7 4 3 2 2 2 1
```

输入：
```
10
1 9 7 6 2 4 7 8 1 3
```
输出：
```
17 9 5 4 3 3 3 2 1
```题目大意： E. 链式反应 有 $ n $ 个怪物站在一行中，第 $ i $ 个怪物有 $ a_i $ 点生命值。 每秒钟，你可以选择一个**活着的**怪物对其发动链状闪电。闪电对其造成 $ k $ 点伤害，并传播到左边（向减少的 $ i $ 方向）和右边（向增加的 $ i $ 方向）的**活着的**怪物，对每个怪物造成 $ k $ 点伤害。当闪电到达一个死怪物或行首/行尾时，它停止。如果一个怪物的生命值严格大于 $ 0 $，则认为它是活着的。 对于每个 $ k $ 从 $ 1 $ 到 $ \max(a_1, a_2, \dots, a_n) $，计算杀死所有怪物所需的最少秒数。 输入输出数据格式： 输入： - 第一行包含一个整数 $ n $（$ 1 \le n \le 10^5 $）——怪物的数量。 - 第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $（$ 1 \le a_i \le 10^5 $）——第 $ i $ 个怪物的生命值。 输出： - 对于每个 $ k $ 从 $ 1 $ 到 $ \max(a_1, a_2, \dots, a_n) $，输出杀死所有怪物所需的最少秒数。 示例输入输出： 输入： ``` 3 5 2 7 ``` 输出： ``` 10 6 4 3 2 2 1 ``` 输入： ``` 4 7 7 7 7 ``` 输出： ``` 7 4 3 2 2 2 1 ``` 输入： ``` 10 1 9 7 6 2 4 7 8 1 3 ``` 输出： ``` 17 9 5 4 3 3 3 2 1 ```