Migrated from Lutece 2859 搭积木

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

今天花花幼儿园的小朋友在玩搭积木的游戏，Kanade 也在陪着小朋友一起玩。

小朋友们打算搭一座桥，他们决定用一些圆柱形积木搭桥身。现在他们有 $n$ 个圆柱形积木，每个积木高度为 $h_i$。小朋友们会使用所有 $n$ 个圆柱形积木。为了桥身美观，小朋友们想要摆好的桥身相邻的两个圆柱形积木高度差的绝对值尽可能大。

Kanade 想知道，对于小朋友们搭出的桥身，所有相邻的两个圆柱形积木高度差的绝对值和最大是多少。

Input

第一行一个整数 $n\ (2\le n\le 10^5)$，表示圆柱形积木个数。

第二行 $n$ 个整数，第 $i$ 个表示第 $i$ 个圆柱形积木的高度 $h_i\ (1\le h_i\le 10^5)$。

Output

一行一个整数，表示所有相邻的两个圆柱形积木高度差的绝对值和的最大值。

Samples

5
5 2 2 2 1

8

Note

对于这个样例，最优的排列方法为 $[2, 5, 2, 1, 2]$，答案为 $|2-5|+|5-2|+|2-1|+|1-2|=8$。

Resources

The 19th UESTC Programming Contest Preliminary