Description

Byteasar has a cottage. He has bought $n$ trees and had them planted in a single row. He dislikes the current order: tall and short ones are mixed, and the arrangement does not meet his aesthetic criteria.

He defines the disorder coefficient of a row as the sum of absolute differences of heights of adjacent trees: $|h_1 - h_2| + |h_2 - h_3| + \cdots + |h_{n-1} - h_n|$, where $h_1, h_2, \cdots, h_n$ are the heights of the trees in order.

Replanting is laborious, so at most two trees may be replanted, i.e., their positions may be swapped. For each position $i$, determine the minimal disorder coefficient that can be achieved by swapping the tree at position $i$ with any other single tree (or by not swapping at all).

Input Format

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

The second line contains $n$ integers $h_i$ ($1 \le h_i \le 100\ 000\ 000$), separated by single spaces, denoting the heights of the trees in order.

Output Format

Output exactly $n$ lines. The $i$-th line should contain a single integer: the minimal disorder coefficient attainable when considering swapping the $i$-th tree with some other tree (or making no change).

5
7 4 5 2 5

7
7
8
7
7

5
1 2 3 4 5

4
4
4
4
4

Hint

Translated by ChatGPT 5