题目描述
小 X 有 n 张标有数字的纸牌,第 i 张纸牌上面的数是 ai,现在小 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 个正整数 ai,表示第 i 张纸牌上的数。注意具有相同数字的纸牌可能有多张。
输出格式
输出一行一个整数,表示答案。
数据范围
本题共有 11 个测试点,每个测试点 10 分。
保证当测试点编号是偶数时,n 也是偶数。
对于测试点 1∼3:1≤n≤10,1≤ai≤106
对于测试点 4∼8:1≤n≤100,1≤ai≤10
对于测试点 9∼11:1≤n≤105,1≤ai≤106