传送门：Luogu
题意讲的很清楚了，不再赘述。
首先我们看一下这个式子。
\[\sum\limits|a_i-a_j| \]添加了绝对值，似乎不太好维护。如果还是看做一位位取的话，我们不知道当前的数比后面的数是小还是大，无法确定正负号。
绝对值不好搞，就拆绝对值。
\[\sum\limits_{i=1}^n (-1)^{[a_i< a_j]}\times a_i \]这个式子可以分开两部分的贡献来看，正数和负数。我们把这两部分拆出来。
\[\sum\limits_{i=1}^n {[a_i> a_j]} a_i -\sum\limits_{i=1}^n[a_i\le a_j]a_i \]一个贪心的思想，就是前面的部分尽量大，后面的部分尽量小。
根据这个贪心，我们不难发现一个结论：把原序列中尽量大的数与尽量小的数匹配是一定不劣的。这样尽量多大的数可以贡献到正数部分。
不难想到前 \(k\) 大都取正是一定最优的。但是我们不知道 \(k\) 应该取什么。根据取前 \(k+1\) 大一定优于前 \(k\) 大，这时思考是否可以二分答案？每次二分前 \(mid\) 大是否满足即可。
现在我们思考一下怎么判断一个序列是否合法。
判断合法相当于给前 \(k\) 大的数打上标记，令这 \(k\) 个数不能满足任意两个数在同一括号匹配里。
根据这样，我们似乎在手推的过程中发现一个重要的结论：似乎只要 \(k\le \frac{n}{2}\) ，序列一定能取到合法值？
oier 不会证明，但我会构造！
——Lgx_q
我们发现可以根据这样一个方法构造出一个合法序列：
-
准备一个栈存数
-
不妨令当前遍历到第 \(x\) 个数：
-
目前栈为空，将 \(a_x\) 入栈。
-
否则分类讨论：
-若栈内的数打了标记 且 \(a_x\) 没有打标记 或 栈内的数没打标记 且 \(a_x\) 打了标记
-