Trees

Byteasar has planted $n$ trees in a single row. He dislikes the order they stand in, because tall and short trees are mixed together.

To measure how untidy the row is, he uses a disorder coefficient. If the heights of the trees from left to right are $h_1, h_2, \ldots, h_n$, the coefficient is

$|h_1 - h_2| + |h_2 - h_3| + \cdots + |h_{n-1} - h_n|$

The smaller this value, the tidier the row.

Replanting is hard work, so Byteasar moves at most two trees: he may pick two trees and swap their positions, or leave the row unchanged. For each tree, find the smallest disorder coefficient that can be reached if that tree is swapped with some other tree, where leaving every tree in place (no swap) is also allowed.

Read the heights of the trees and, for each tree, output the smallest disorder coefficient obtainable by swapping it with another tree or by making no change at all.

The first line contains one integer $n$ ($2 \le n \le 50000$).

The second line contains $n$ integers $h_1, h_2, \ldots, h_n$ ($1 \le h_i \le 10^8$), separated by single spaces, giving the heights of the trees from left to right.

Print exactly $n$ lines. Line $i$ must contain a single integer: the smallest disorder coefficient that can be attained when tree $i$ is considered for replanting (swapped with one other tree, or left in place).

For a fixed tree $i$ you have two choices: leave the whole row unchanged, or swap tree $i$ with exactly one other tree. Report the smaller resulting coefficient.

In the first example the value $7$ can be reached by swapping trees $1$ and $4$, trees $2$ and $5$, or trees $4$ and $5$, so trees $1$, $2$, $4$ and $5$ all reach $7$; only tree $3$ cannot do better than $8$.

In the second example every swap increases the coefficient, so the best choice for every tree is to change nothing, and each answer equals the initial coefficient $4$.