题目背景

挖矿的时候踢断电源线是一种怎样的体验?

题目描述

在某台有 $k$ 个 CPU 的计算机中，有 $n$ 个计算任务等待执行。

$a_i$ 为第 $i$ 个任务的优先级，方便起见， $a$ 为一个排列。

现在，要将这些任务分配给 CPU 去解决。

由于内存等原因，一个 CPU 只能负责连续一段的任务，并且要按 (从左到右的) 顺序执行。

在某个 CPU 内，无序度定义为：前者先执行，而后者优先级高的任务对的个数。

请最小化每个 CPU 的无序度之和。

输入格式

第一行两个整数 $n,k$ ，分别表示任务个数和 CPU 个数。

第二行 $n$ 个整数，表示 $a_{1\sim n}$ 。

输出格式

输出一个整数，表示最小的无序度之和。

5 1
1 5 4 2 3

5

5 2
1 5 4 2 3

1

8 3
1 3 5 2 7 4 8 6

4

提示

(保证 $k\leq n$ ， #6~10时限2S)

样例解释:

• 样例1

此时只能把所有任务交给单独的一个 CPU。

第一个任务和其他所有任务都形成无序任务对。

此外最后两个任务也形成无序任务对，共 $5$ 个。

• 样例2

第一个 CPU 单独处理任务 $1$ ，无序度为 $0$ ;

第二个 CPU 处理 $\{5,4,2,3\}$ 无序度为 $1$ 。