E. 连锁反应

时间限制：$3$ 秒
内存限制：$512$ 兆字节

题目描述

有 $n$ 只怪物排成一排，第 $i$ 只怪物拥有 $a_i$ 点生命值。

每一秒你可以选中一只存活的怪物释放连锁闪电： 闪电对选中怪物造成 $k$ 点伤害，同时向向左、向右依次传播； 每遇到一只存活怪物就对其也造成 $k$ 点伤害； 当闪电碰到已死亡怪物、队伍左端或队伍右端时，传播立即停止。

怪物生命值严格大于 $0$ 时视为存活。

举例说明

有 $3$ 只怪物，生命值 $[5,2,7]$，$k=3$。 可以用 $4$ 秒全歼所有怪物：

1. 对第 $3$ 只放闪电 → 血量变为 $[2,-1,4]$
2. 对第 $1$ 只放闪电 → 血量变为 $[-1,-1,4]$
3. 对第 $3$ 只放闪电 → 血量变为 $[-1,-1,1]$
4. 对第 $3$ 只放闪电 → 血量变为 $[-1,-1,-2]$

现在要求： 对每一个 $k$，取值范围为 $1 \le k \le \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$），表示每只怪物的生命值。

输出格式

依次输出 $k=1,2,\dots,\max a_i$ 对应的最小秒数，数字之间用空格隔开。

样例输入输出

样例输入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