On Backstab Boulevard, 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 Backstab Boulevard are famously petty, and they cannot stand a lantern with no strong opinions: not the brightest, not the dimmest, just $\textit{meh}$. If the people in houses $i$ and $k$ both still have their lights on, with $i < j < k$, and the lantern of house $j$ hangs neither the highest nor the shortest of the three, that is $h_i < h_j < h_k$ or $h_i > h_j > h_k$, then the two of them team up against house $j$ and sabotage it. They sneak over at night, unscrew the bulb, and the lantern of house $j$ goes dark for good.

A saboteur needs a working lantern to find their way in the dark, so a house whose lantern is already off can never take part in a sabotage again. The residents sabotage as many times as they like, and they are always happy to keep going. Every house is both a potential victim and a potential accomplice.

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

stdin

3
1 2 3

stdout

3 3 0

Note

There are $6$ possible ranges $[l, r]$:

• $[1, 1]$, $[2, 2]$ and $[3, 3]$ each contain a single lit lantern. A sabotage needs three lit houses, so nothing happens and $f(l, r) = 1$.
• $[1, 2]$ and $[2, 3]$ each contain only two lit lanterns. Again no sabotage is possible, so $f(l, r) = 2$.
• $[1, 3]$ contains all three lanterns, and $h_1 < h_2 < h_3$ ($1 < 2 < 3$). The residents of houses $1$ and $3$ team up and sabotage house $2$, so its lantern goes dark. Only two lanterns are left on, so no further sabotage is possible, and $f(1, 3) = 2$.