题目描述

译自 POI 2007 Stage 1.「Drzewa」

有 $n$ 棵树的高度分别为 $h_1, h_2, ..., h_n$。定义其不整齐程度为 $\lvert h_1 - h_2 \rvert + \lvert h_2 - h_3 \rvert \ldots \lvert h_{n-1} - h_n \rvert$。对其中每一棵树，求其与另一棵树交换（也可以不交换）后不整齐程度的最小值。

输入格式

第一行一个整数 $n (1 \le n \le 50\ 000)$，表示树的个数。

接下来一行有 $n$ 个整数 $h_i$ （$1 \le h_i \le 100\ 000\ 000$），表示树的高度。

输出格式

输出 $n$ 行，每行一个整数，表示将第 $i$ 棵树与另一棵树交换（也可以不交换）后不整齐程度的最小值。

5
7 4 5 2 5

7
7
8
7
7

5
1 2 3 4 5

4
4
4
4
4