Problem Statement

There are $N$ slimes lined up in a row from left to right. For $i = 1, 2, \ldots, N$, the $i$-th slime from the left has size $A_i$. For each $K = 1, 2, \ldots, N$, solve the following problem.

Takahashi is the $K$-th slime from the left in the initial state. Find the maximum size that he can have after performing the following action any number of times, possibly zero:

• Choose a slime adjacent to him that is strictly smaller than him, and absorb it. As a result, the absorbed slime disappears, and Takahashi's size increases by the size of the absorbed slime.

When a slime disappears due to absorption, the gap is immediately closed, and the slimes that were adjacent to the disappearing slime (if they exist) become adjacent (see the explanation in Sample Input 1).

Constraints

• $2 \leq N \leq 5 \times 10^5$
• $1 \leq A_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Print the answers $B_K$ for each $K = 1, 2, \ldots, N$, separated by spaces, in the following format:

B_1 B_2 \ldots B_N