Description

　　CDQZ是一个偏远的小学校，FGD在学校里中了一排树。他却不喜欢这些树的顺序，因为他们高高矮矮显得那么
参差不齐。FGD定义这些树的不整齐程度为相邻两树的高度差的和。设树高分别为h1,h2,h3,…,hn。那么不整齐程
度定义为：|h1-h2|+|h2-h3|+……+|hn-1-hn|。不过，重新栽种这些树是一件麻烦的事情，所以FGD最多只想交换
其中两个树的位置。现在请你帮助他，他应该怎么交换使得整个一排树的不整齐程度最小。

Input

　　第一行包含一个整数n(2<=n<=50000)，接下来第二行包含n个正整数h1,h2,h3,…,hn，分别表示树的高度。（1
<=hi<=100000000）

Output

　　应该包含n行，每行一个整数，第i行表示若交换的其中一棵树编号为i，则能获得的最小不整齐程度为多少。

Sample Input

Sample Output

Hint

Source