Problem Background

What is the experience of kicking the power cord during mining?

Problem Description

In a computer with $k$ CPUs, there are $n$ computational tasks waiting to be executed.

$a_i$ represents the priority of the $i$-th task, and for convenience, $a$ is a permutation.

Now, these tasks need to be assigned to the CPUs for execution.

Due to memory constraints, a CPU can only handle a continuous segment of tasks and must execute them in order (from left to right).

Within a CPU, the disorder degree is defined as the number of task pairs where the former is executed first but has a lower priority than the latter.

Please minimize the sum of the disorder degrees for each CPU.

Input Format

The first line contains two integers $n$ and $k$, representing the number of tasks and the number of CPUs, respectively.

The second line contains $n$ integers, representing $a_{1 \sim n}$.

Output Format

Output a single integer, representing the minimum sum of disorder degrees.

Sample Input and Output

Sample Input #1

5 1
1 5 4 2 3

Sample Output #1

5

Sample Input #2

5 2
1 5 4 2 3

Sample Output #2

1

Sample Input #3

8 3
1 3 5 2 7 4 8 6

Sample Output #3

4

Notes

(It is guaranteed that $k \leq n$. For test cases #6~10, the time limit is 2 seconds.)

Sample Explanation:

• Sample 1

Here, all tasks must be assigned to a single CPU.

The first task forms a disordered pair with every other task.

Additionally, the last two tasks also form a disordered pair, totaling 5.

• Sample 2

The first CPU handles task $1$ alone, with a disorder degree of $0$;

The second CPU handles $\{5, 4, 2, 3\}$ with a disorder degree of $1$.

见题面 Input 部分

见题面 Output 部分