[CmdOI2019]任务分配问题

题目背景

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

题目描述

在某台有$k$个CPU的计算机中,有$n$个计算任务等待执行。 $a_i$为第$i$个任务的优先级,方便起见,$a$为一个排列。 现在,要将这些任务分配给CPU去解决。 由于内存等原因,一个CPU只能负责连续一段的任务,并且要按(从左到右的)顺序执行。 **在某个CPU内**,无序度定义为 : 前者先执行,而后者优先级高的任务对的个数。 请最小化每个CPU的无序度之和。

输入输出格式

输入格式


第一行两个整数$n,k$,分别表示任务个数和CPU个数。 第二行$n$个整数,表示$a_{1...n}$

输出格式


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

输入输出样例

输入样例 #1

5 1
1 5 4 2 3

输出样例 #1

5

输入样例 #2

5 2
1 5 4 2 3

输出样例 #2

1

输入样例 #3

8 3
1 3 5 2 7 4 8 6

输出样例 #3

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;