Task Scheduling on Multi-CPU

Consider a computer with (k) CPUs and (n) tasks waiting to be executed. The tasks are arranged in a fixed order with priorities (a_1, a_2, \dots, a_n), where (a) is a permutation of ({1,2,\dots,n}).

The tasks must be partitioned into exactly (k) contiguous segments. Each segment is assigned to one CPU and the tasks in that segment are executed in order (from left to right).

Inside a CPU, the unordered degree is defined as the number of pairs ((i,j)) within the segment (with (i < j)) for which the earlier task has a lower priority than the later task. In other words, if a segment covers indices (l) to (r), its cost is [ cost(l,r) = #{(i,j) \mid l \le i < j \le r \text{ and } a_i < a_j},. ]

Your task is to partition the sequence into (k) contiguous segments so that the sum of the unordered degrees (costs) of all segments is minimized.

Input/Output Format: The input consists of two lines. The first line contains two integers (n) and (k). The second line contains (n) integers representing the permutation (a).

Output the minimum possible sum of unordered degrees among the (k) segments.

Note: Use (\LaTeX) format for any formulas.

inputFormat

The first line contains two integers (n) and (k) ( (1 \le k \le n)). The second line contains (n) integers (a_1, a_2, \dots, a_n) representing a permutation of ({1,2,\dots,n}).

outputFormat

Output a single integer: the minimum possible sum of unordered degrees among the (k) segments.

sample

3 2
3 1 2

0