袜子 2

题目描述

高桥君有 $N$ 双袜子,其中第 $i$ 双由两只颜色为 $i$ 的袜子组成。 一天,在整理衣柜抽屉后,高桥君发现自己丢失了颜色分别为 $A_1, A_2, \dots, A_K$ 的各一只袜子,于是他决定用剩下的 $2N-K$ 只袜子组成 $\lfloor\frac{2N-K}{2}\rfloor$ 双新袜子,每双由两只袜子组成。 由颜色为 $i$ 的袜子和颜色为 $j$ 的袜子组成的一双袜子的「奇怪程度」定义为 $|i-j|$,高桥君希望使总的奇怪程度最小。

求用剩下的袜子组成 $\lfloor\frac{2N-K}{2}\rfloor$ 双袜子时,可能达到的最小总奇怪程度。 注意,如果 $2N-K$ 是奇数,将有一只袜子不参与配对。

输入格式

输入按以下格式从标准输入给出:

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_K$

输出格式

以整数形式输出最小的总奇怪程度。

样例

4 2
1 3

2

下面,用 $(i,j)$ 表示由颜色为 $i$ 的袜子和颜色为 $j$ 的袜子组成的一双袜子。

颜色 $1, 2, 3, 4$ 的袜子分别有 $1, 2, 1, 2$ 只。 组成 $(1,2),(2,3),(4,4)$ 这三双后,总奇怪程度为 $|1-2|+|2-3|+|4-4|=2$,这是最小值。

5 1
2

0

最优方案是组成 $(1,1),(3,3),(4,4),(5,5)$,并把一只颜色为 $2$ 的袜子作为剩余(不参与任何配对)。

8 5
1 2 4 7 8

2

数据范围

• $1\leq K\leq N \leq 2\times 10^5$
• $1\leq A_1 \lt A_2 \lt \dots \lt A_K \leq N$
• 输入中的所有值均为整数。