Monster Train 2

题目描述

Monster Train 2 is an excellent roguelike deck-building game. During combat, friendly units attack enemy units every turn. Consider a friendly unit that has all three effects Quick, Trample, and Sweep: it attacks before enemy units, hits every enemy unit, and carries excess damage onward.

There are $n$ enemy units on the same floor, arranged from front to back and numbered $1, 2, \ldots, n$ in that order. The $i$-th enemy unit has $a_i$ Health, where $a_i$ is a positive integer.

For this problem, the unit's Attack is a non-negative integer $B$. At the beginning of its turn, the combined effect of Quick, Trample, and Sweep is modeled as follows:

1. First, all enemy units simultaneously take $B$ damage.
2. Every enemy unit whose remaining Health is non-positive dies in the first step. If its remaining Health is negative, it produces $B-a_i$ excess damage; if its remaining Health is exactly $0$, it produces no excess damage.
3. Each enemy unit that died in the first step sends its excess damage to the nearest enemy unit behind it that survived the first step. If there is no surviving enemy unit behind it, the damage wraps around to the frontmost surviving enemy unit.
4. All excess damage is applied simultaneously and is carried over only once. An enemy unit killed by excess damage does not pass on any further damage.

If no enemy unit survives the first step, all of them are immediately considered defeated.

For every $m=1, 2, \ldots, n$, suppose that only the first $m$ enemy units are present. Find the minimum Attack $B$ required for the friendly unit to defeat all of them in this turn.

输入格式

The first line contains one integer $n$ ($1 \le n \le 5 \cdot 10^5$), the number of enemy units.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$), the initial Health values of the enemy units in front-to-back order.

输出格式

Output $n$ integers. The $m$-th integer must be the answer when only the first $m$ enemy units are present.

样例输入 #1

5
1 4 2 5 3

样例输出 #1

1 3 3 4 4