小 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 张纸牌上的数。注意具有相同数字的纸牌可能有多张。

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

【样例2解释】

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

【数据规模与解释】

保证当测试点编号是偶数时，n 也是偶数。

对于测试点 1-3： 1 \leq n \leq 10,1 \leq a[i] \leq 1000000

对于测试点 4-8： 1 \leq n<=100,1 \leq a[i] \leq 10

对于测试点 9-11：1 \leq n \leq 100000,1 \leq a[i] \leq 1000000

23年常州市赛T5

市赛