#B4220. [常州市程序设计小能手 2023] 洗牌

[常州市程序设计小能手 2023] 洗牌

题目背景

搬运自 http://czoj.com.cn/p/677。数据为民间数据。

题目描述

小 X 有 nn 张标有数字的纸牌,第 ii 张纸牌上面的数是 aia_i,现在小 X 想通过洗牌打乱它们的顺序。

对于一个洗牌后的顺序,小 X 觉得相邻两张纸牌上数的差的绝对值之和越大,牌就洗的 越乱。

举个例子:现在有 44 张纸牌,纸牌上的数依次为 [1,2,3,4][1,2,3,4]

假设洗完牌后,纸牌上的数依次 [4,3,2,1][4,3,2,1],相邻两张纸牌上数的差的绝对值之和为 $\left|4-3\right|+\left|3-2\right|+\left|2-1\right|=1+1+1=3$。

假设洗完牌后,纸牌上的数依次 [2,4,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][2,4,1,3] 的顺序比 [4,3,2,1][4,3,2,1] 更乱。

小 X 想要问问你,对于所有顺序,相邻两张纸牌上数的差的绝对值之和最大能是多少。

输入格式

第一行 11 个正整数 nn,表示纸牌的张数。 第二行 nn 个正整数 aia_i,表示第 ii 张纸牌上的数。注意具有相同数字的纸牌可能有多张。

输出格式

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

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

提示

本题共有 1111 个测试点。

保证当测试点编号是偶数时,nn 也是偶数。

测试点编号 nn aia_i
131\sim3 1n101\le n\le 10 1ai1061\le a_i\le10^6
484\sim8 1n1001\le n\le 100 1ai101\le a_i\le 10
9119\sim11 1n1051\le n\le10^5 1ai1061\le a_i\le 10^6