题目描述

一个删数游戏，一共有 $3N$ 个数，现在请你删除其中的 $N$ 个数（不一定要连续删除），但是删除以后，留下来的 $2N$ 个数相对顺序不能改变。

我们定义 $V$ 为删除 $N$ 个数后，前 $N$ 个数的和减去后 $N$ 个数的和的值。请问你要如何删除才能使得 $V$ 最大。

$N \le 10^5$, 所有数的绝对值小于等于 $10^9$.

样例

输入

2 
3 1 4 1 5 9

输出

1

解释

可以删去第一个 $1$ 和最后一个 $9$，$V = (3 + 4) - (1 + 5) = 1$.

我的 Naive 想法

感觉是先排序前后 $N$ 个数，然后考虑怎么删数最优。

可以删前 $N$ 个的最小值，让中间那一段的最左的那个数进入前面 $N$ 个。

也可以删后 $N$ 个的最大值，让中间那一段的最右的那个数进入后面 $N$ 个。

然后可以用堆维护最大最小，复杂度大概 $\mathcal{O}(N \log_2 N)$?

问题

想问一下有没有线性做法，也许依赖单调性？