题目描述

小 X 有 n 张标有数字的纸牌，第 i 张纸牌上面的数是 a[i]，现在小 X 想通过洗牌打乱它们的顺序。 
对于一个洗牌后的顺序，小 X 觉得相邻两张纸牌上数的差的绝对值之和越大，牌就洗的越乱。
举个例子：现在有 4 张纸牌，纸牌上的数依次为 1,2,3,4。 
假设洗完牌后，纸牌上的数依次 4,3,2,1，相邻两张纸牌上数的差的绝对值之和为 |4-3|+|3-2|+|2-1|=1+1+1=3。 
假设洗完牌后，纸牌上的数依次 2,4,1,3，相邻两张纸牌上数的差的绝对值之和为 |4-2|+|4-1|+|3-1|=2+3+2=7。 
那么小 X 就会觉得 2,4,1,3 的顺序比 4,3,2,1 更乱。 
小 X 想要问问你，对于所有顺序，相邻两张纸牌上数的差的绝对值之和最大能是多少。

输入格式

第一行 1 个正整数 n，表示纸牌的张数。
第二行 n 个正整数 a[i]，表示第 i 张纸牌上的数。注意具有相同数字的纸牌可能有多张。

输出格式

输出一行一个整数，表示答案。

样例数据1

input

4
1 2 3 4

output

7

样例数据2

input

5
1 2 3 4 5

output

11

样例解释

一种可行的顺序是 3 5 1 4 2

样例数据3

input

10
1 2 3 4 5 6 7 8 9 10

output

49

数据范围

保证当测试点编号是偶数时，n 也是偶数。 
对于测试点 1-3：1<=n<=10,1<=a[i]<=1000000 
对于测试点 4-8：1<=n<=100,1<=a[i]<=10 
对于测试点 9-11：1<=n<=100000,1<=a[i]<=1000000