题目背景

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

题目描述

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

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

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

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

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

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

输入格式

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

第二行$n$个整数,表示$a_{1...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

提示

| 测试点编号 | 　n　 | 　k　 | | :--: | :--: | :--: | :--: | :--: | | 1~2 | 25000 | 1 | | 3 | 25000 | 2 | | 4~5 | 1000 | 10 | | 6~10 | 25000 | 25 |

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

样例解释:

• 样例1

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

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

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

• 样例2

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

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