题目描述

有 $n$ 棵树的高度分别为 $h_1, h_2, \ldots, 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

样例 2

输入

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$。