CF1954E Chain Reaction

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.

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.

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.