题目描述

译自 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$ 棵树与另一棵树交换（也可以不交换）后不整齐程度的最小值。

样例 1

5
7 4 5 2 5

7
7
8
7
7

5
1 2 3 4 5

4
4
4
4
4

第一个样例中最小的不整齐程度为 $7$，可以交换树 $1,4$ 或 $2,5$ 或 $4,5$ 实现，因此对 $1,2,4,5$ 这四棵树来说答案是 $7$，只有对第 $3$ 棵树来说答案是 $8$，可以通过交换树 $3,4$ 来实现。

第二个样例中无论交换哪两棵树都会使答案变大，因此最优方案都是不交换，不整齐程度均为 $4$。