Circular Milk Passing

Farmer John's $N$ ($1\le N\le 5\cdot10^5$) cows are arranged in a circle. The $i$-th cow has a bucket with an integer capacity $a_i$ ($1\le a_i\le 10^9$) liters, and initially every bucket is full. Every minute, all cows simultaneously pass all the milk in their bucket to the next cow in clockwise order: for $1\le i<N$, cow $i$ sends her milk to cow $i+1$, and cow $N$ sends her milk to cow $1$. After receiving the milk, each cow retains milk up to the capacity of her bucket, and any excess is spilled and lost.

Formally, let $x_i(0)=a_i$ denote the milk in cow $i$ initially. Then for each minute $t\ge1$, the milk in cow $i$ is updated as follows: [ x_1(t)=\min\Bigl(a_1,;x_{N}(t-1)\Bigr),\quad x_i(t)=\min\Bigl(a_i,;x_{i-1}(t-1)\Bigr)\quad(2\le i\le N). ] Note that this is equivalent to saying that after $t$ minutes, cow $i$ holds [ x_i(t)=\min\Bigl{a_i, a_{i-1},\dots, a_{i-t}\Bigr}, ] where the indices are taken modulo $N$ (with the obvious adjustment when $t\ge N$, since the circle has only $N$ cows).

Your task is to compute, for each minute $t=1,2,\ldots,N$, the total amount of milk remaining among all cows, i.e. compute [ S(t)=\sum_{i=1}^N x_i(t). ]

Input Format: The first line contains an integer $N$. The second line contains $N$ space‐separated integers $a_1,a_2,\dots,a_N$, which are the capacities of the buckets in clockwise order.

Output Format: Output $N$ lines. The $t$-th line (for $1\le t\le N$) should contain a single integer, the value of $S(t)$ after $t$ minutes.

Note: Although $N$ can be large (up to $5\cdot10^5$) and the capacities can be as large as $10^9$, the process quickly propagates the minimum value around the circle. For the purposes of this problem and the provided test cases, however, you may assume that a simulation with $N$ iterations is sufficient.

inputFormat

Input Format:

• The first line contains an integer $N$.
• The second line contains $N$ space‐separated integers $a_1,a_2,\dots,a_N$.

outputFormat

Output Format:

• Output $N$ lines. The $t$-th line (for $1\le t\le N$) contains the total amount of milk remaining after $t$ minutes.

sample

4
5 7 3 6

16
14
12
12