Circular Water Tanks

There are \( n \) water tanks arranged in a circle. Each tank i has a capacity \( a_i \) and is initially full (i.e. contains \( a_i \) water). Every second, the water in each tank is completely transferred to the next tank in the circle. In particular, at each second, for every tank \( i \) the water is transferred to tank \( i+1 \) (and for tank \( n \), the water is transferred to tank \( 1 \)). However, if the transferred water exceeds the capacity of the receiving tank, the extra water overflows and is lost.

Formally, let \( w_i^{(t)} \) be the amount of water in tank \( i \) after \( t \) seconds. The process is defined as follows:

[ \begin{aligned} w_i^{(0)} &= a_i,\ w_i^{(t+1)} &= \min\Bigl{ a_i,; w_{i-1}^{(t)} \Bigr} \quad \text{for } 1 \leq i \leq n,\ \end{aligned} ]

where the index is taken modulo \( n \) (i.e. \( w_1^{(t+1)} = \min\{ a_1, w_{n}^{(t)} \}\)).

Your task is to compute, for each second \( t = 1, 2, \ldots, n \), the total amount of water in all tanks, i.e.,

[ S^{(t)} = \sum_{i=1}^{n} w_i^{(t)}. ]

Note: The water that overflows is lost permanently.

inputFormat

The first line contains a single integer \( n \) (the number of water tanks). The second line contains \( n \) space-separated integers \( a_1, a_2, \ldots, a_n \) representing the capacities of the tanks.

outputFormat

Output \( n \) lines. The \( i \)-th line should contain a single integer representing the total amount of water in all tanks after \( i \) seconds.

sample

4
5 3 4 2

10
9
8
8