Byteasar 有一间小屋。最近，他买了 $n$ 棵树，并将它们种成了一排。然而，Byteasar 并不喜欢这些树种植的顺序。他特别反感高矮不一的树混在一起，这种布局不符合他的审美标准。

Byteasar 发明了一个“混乱系数”，以便让园丁理解他的意图：该系数的值越小，树木排列得就越美观。其定义如下：$|h_1-h_2|+|h_2-h_3|+\dots+|h_{n-1}-h_n|$，其中 $h_1, h_2, \dots, h_n$ 是这一排树从左到右的高度。

重新种植是一项非常繁重且麻烦的工作，因此 Byteasar 命令园丁最多重新种植两棵树（即交换它们的位置）。园丁的任务是选择一对树进行交换，使得混乱系数最小。

园丁不确定他是否选择了正确的树木对，他担心如果弄错了可能会丢掉工作。请帮助他：对于每一棵树，计算将其与任意其他树交换位置后，所能达到的最小混乱系数。

编写一个程序：

• 从标准输入读取一排树的高度；
• 对于每一棵树，计算将其与某棵树交换（或保持不变）后所能达到的最小混乱系数；
• 将结果写入标准输出。

输入格式

标准输入的第一行包含一个整数 $n$ ($2 \le n \le 50\,000$)。第二行包含 $n$ 个整数 $h_i$ ($1 \le h_i \le 100\,000\,000$)，由空格分隔，表示这一排树的高度。

输出格式

输出应包含恰好 $n$ 行。第 $i$ 行应包含一个整数，表示考虑交换第 $i$ 棵树时所能达到的最小混乱系数。

样例

输入格式 1

5
7 4 5 2 5

输出格式 1

7
7
8
7
7

说明

在第一个样例中，通过交换第 1 棵和第 4 棵树、第 2 棵和第 5 棵树，或者第 4 棵和第 5 棵树，可以将混乱系数降为 7。因此，对于上述树木（1, 2, 4, 5）中的任意一棵，与其对应的树交换后均可得到 7。只有对于第 3 棵树，其能达到的最优结果较大，为 8。在第二个样例中，任何交换都会增加混乱系数的值，因此不应进行任何更改；所有混乱系数均为初始值 (4)。