This problem is different from Problem B, "Backstab Boulevard". In particular, pay close attention to the second paragraph.

On Spite Street, there are $n$ houses numbered from $1$ to $n$, and in each house lives exactly one person. Each house $i$ has a lantern at height $h_i$. The heights are distinct integers from $1$ to $n$. Initially, all the lanterns are on.

The residents of Spite Street have been feuding over property lines for decades, and the only thing they hate more than each other is a lantern that is smugly 'in between'. Consider a lit house $j$. Let $a$ be the closest lit house to its left and $b$ be the closest lit house to its right, skipping over any dark houses. If $h_a < h_j < h_b$ or $h_a > h_j > h_b$, the neighbors in $a$ and $b$ cannot stand it, so they team up to sabotage house $j$. If a house has no lit neighbors on one side, it cannot be ganged up on. They sneak over at night, unscrew the bulb, and the lantern of house $j$ goes dark for good. The residents may do this as many times as they like, one house at a time.

One evening, a blown fuse hits the street: all the lanterns outside a range $[l, r]$ suddenly go off, so only the lanterns of houses $l$ to $r$ are still on. Because of this crisis, the residents of these houses go mad and sabotage night after night, as many nights as they want. Let $f(l, r)$ be the smallest number of lanterns that can remain on if they choose the order of the sabotages optimally.

The blackout could hit any range of houses, so the residents want to be ready for every possibility. For each $k$ from $1$ to $n$, count the pairs $(l, r)$ with $1 \leq l \leq r \leq n$ such that $f(l, r) = k$.

Input

The first line contains an integer $n \ (1 \leq n \leq 5 \cdot 10^5)$, the number of houses.

The second line contains distinct integers $h_1, h_2, \dots, h_N$, the heights of the lanterns. They form a permutation of the integers from $1$ to $n$.

Output

Print $n$ integers separated by spaces. The $k$-th integer is the number of pairs $(l, r)$ with $1 \leq l \leq r \leq n$ such that $f(l, r) = k$.

Example 1

stdin

3
1 2 3

stdout

3 3 0

Example 2

stdin

4
1 3 2 4

stdout

4 3 2 1

Note

In the first example, the only range in which a sabotage is possible is $[1, 3]$. House $2$ is lit, its closest lit neighbors are houses $1$ and $3$, and $h_1 < h_2 < h_3$ ($1 < 2 < 3$), so houses $1$ and $3$ can sabotage house $2$.

In the second example, no sabotage is ever possible.