You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

输出格式

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

4 
1 2 3 4

7

5
1 2 3 4 5

11

10
1 2 3 4 5 6 7 8 9 10

49

数据范围

本题共有 $11$ 个测试点，每个测试点 $10$ 分。

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

对于测试点 $1\sim 3$：$1\le n\le 10,1\le a_i\le 10^6$

对于测试点 $4\sim 8$：$1\le n\le 100,1\le a_i\le 10$

对于测试点 $9\sim 11$：$1\le n\le 10^5,1\le a_i\le 10^6$