B4220 [常州市赛 2023] 洗牌

搬运自 。数据为民间数据。

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

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

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

本题共有 $11$ 个测试点。 保证当测试点编号是偶数时，$n$ 也是偶数。 |测试点编号|$n$|$a_i$| |:-:|:-:|:-:| |$1\sim3$|$1\le n\le 10$|$1\le a_i\le10^6$| |$4\sim8$|$1\le n\le 100$|$1\le a_i\le 10$| |$9\sim11$|$1\le n\le10^5$|$1\le a_i\le 10^6$|