Minimizing Disorder Coefficient

Byteasar has a cottage and recently planted n trees in a row. However, he is not satisfied with the order because tall and short trees are mixed up. He defines the disorder coefficient of the row as:

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

The gardener is allowed to swap at most two trees (i.e. perform at most one swap) to reduce the disorder. For each tree (at position i), determine the minimal disorder coefficient that can be obtained by swapping that tree with any other tree (or even leaving it in place).

Task: Given the heights of the trees, for each tree output the minimum disorder coefficient achievable if it is swapped with some other tree (or not swapped if that is optimal).

inputFormat

The first line of input contains a single integer n — the number of trees.

The second line contains n space-separated integers h₁, h₂, ..., h_n representing the heights of the trees in the row.

You may assume that n is small enough for a solution with a double loop to pass.

outputFormat

Output a single line with n space-separated integers. The i-th integer is the minimal disorder coefficient that may be attained after swapping the tree at position i with another tree (or not swapping if that is optimal).

The disorder coefficient is defined as:

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

sample

3
2 1 3

2 2 3