[POI2007]树Drz

CDQZ 是一所偏远的小学，FGD 在学校里种了一排树。由于这些树高低不一，他认为它们看起来很不整齐。

设这 $n$ 棵树的高度依次为 $h_1,h_2,\ldots,h_n$，FGD 将这排树的不整齐程度定义为相邻两棵树高度差的绝对值之和，即

$$|h_1-h_2|+|h_2-h_3|+\cdots+|h_{n-1}-h_n|。$$

重新栽种树木十分麻烦，因此 FGD 最多只愿意交换两棵树的位置。

对于每棵树，你需要求出：如果交换操作涉及这棵树，或者不进行交换，所能得到的最小不整齐程度。

输入格式

第一行包含一个整数 $n$，表示树的数量。

第二行包含 $n$ 个正整数 $h_1,h_2,\ldots,h_n$，依次表示每棵树的高度。

输出格式

输出 $n$ 行，每行包含一个整数。

第 $i$ 行表示交换操作涉及编号为 $i$ 的树，或者不进行交换时，能够得到的最小不整齐程度。

样例输入

样例 $1$：

5
7 4 5 2 5

样例 $2$：

5
1 2 3 4 5

样例输出

样例 $1$：

7
7
8
7
7

样例 $2$：

4
4
4
4
4

数据范围

• $2\le n\le 5\times 10^4$；
• $1\le h_i\le 10^8$。

来源与许可

本题为 POI 2007 试题「树」，题面与测试数据整理自 BZOJ。

样例 1

输入

5
7 4 5 2 5

输出

7
7
8
7
7

样例 2

输入

5
1 2 3 4 5

输出

4
4
4
4
4