Background

What does it feel like to kick off the power cable while mining?

Problem Description

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

Let $a_i$ be the priority of the $i$-th task. For convenience, $a$ is a permutation.

Now, these tasks need to be assigned to the CPUs to be processed.

Due to reasons such as memory limits, one CPU can only handle one continuous segment of tasks, and it must execute them in order (from left to right).

Within a single CPU, the disorder is defined as the number of pairs of tasks where the former is executed earlier, but the latter has a higher priority.

Minimize the sum of disorders over all CPUs.

Input Format

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

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

Output Format

Output one integer, representing the minimum possible sum of disorders.

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

Hint

Sample Explanation

• Sample #1

  In this case, all tasks can only be assigned to a single CPU.

  The first task forms disorder pairs with all other tasks; the last two tasks also form a disorder pair, for a total of $5$.

• Sample #2

  The first CPU processes task $1$ alone, with disorder $0$.

  The second CPU processes $\{5,4,2,3\}$, with disorder $1$.

Constraints and Notes

For all testdata, it is guaranteed that $1\leq n\leq 2.5\times 10^4$, $1\leq k\leq 25$, $a\leq n$.

Translated by ChatGPT 5