F. àPaPdnarG
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

GrandPaPà gives you an array $$$A$$$ of $$$N$$$ elements. Your task is to split this array into $$$K$$$ non-intersecting non-empty contiguous subarrays such that the sum of all subarrays costs is minimum. The cost of an array $$$V$$$ is the number of pairs of indices $$$(i,j)$$$ such that i<j and $$$V_i \gt V_j.$$$

Input

Input consists of numbers $$$N,K$$$ and an array $$$A$$$ of $$$N$$$ elements.

Output

Print one integer : The minimum cost you can have.

Scoring
  • For all test data $$$N \cdot K \le 10^6$$$ , $$$1\le K \le N , -10^9 \le A_i \le 10^9$$$
  • For 5 points $$$K = 1$$$.
  • For another 10 points $$$K = 2$$$.
  • For another 20 points $$$N,K \le 100$$$
  • For the remaining test data , there are no further restrictions
Example
Input
4 2
4 3 2 1
Output
2
Note

The optimal split is [4,3][2,1]. The cost of this split is $$$1+1=2$$$ , which is minimum possible.