P3453 [POI 2007] DRZ-Trees

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).

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 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).

Translated by ChatGPT 5