LARMY  Lannister Army
"A Lannister Always Pays His Debts."
That's true, now here is a chance for you to get paid by Jaime Lannister.
In Jaime's army there are total N number of warriors.
And all them are standing in a single row.
Now Jaime wants to convey a message to his warriors. But it's very difficult to convey a message if warriors are standing in a single row.
So, Jaime wants to break that single row into K rows. Such that in each row at least one warriors should be there.
Also, there is an amount of unhappiness associated with each warrior x which is equal to : number of warriors in front of x (in his row) whose height is greater than the height of x. And, total unhappiness is sum of unhappiness of all warriors. Jaime wants that his army should be happy as much as possible.
Now, Jaime wants you to break the single row into K rows such that total unhappiness should be minimum.
Note : You just have to break the row, you are not allowed to change the position of the warriors.
Input Format
First line of input contain two integers N & K.
Second line of input contain N number of integers, i th of which denote height of i th warrior standing in that single row (represented as H[i]).
Constraints
1 <= N <= 5000
1 <= K <= N
1 <= H[i] <= 10^5
Output Format
Output the minimum possible value of "total unhappiness".
Examples
Input
6 3
20 50 30 60 40 100
Output
0
Explanation
Break as :
Row 1 : 20 50
Row 2 : 30 60
Row 3 : 40 100
Input
8 3
20 50 30 60 40 100 5 1
Output
2
Explanation
Row 1 : 20 50 30 60, Unhappiness = 1
Row 2 : 40 100, Unhappiness = 0
Row 3 : 5 1, Unhappiness = 1
Total = 2
Update : Time limit increased.
hide comments
talha_taki:
20220506 23:41:57
try using knuth optimization 

moh.amr:
20200709 13:52:31
Please modify the time limit, so that languages other than C++ pass. Last edit: 20200709 14:06:50 

urielguz33:
20200618 08:54:49
Very cool problem. 

itssanat:
20200423 08:28:12
Nice problem :)


bad_code:
20200316 11:59:43
The time limit is tight. My O(n^2 logn + nklogn) solution TLEd, but O(n^2 + nklogn) one passed 

aditya_305:
20191211 16:48:01
I don't know why it is giving TLE.... My solution is to use divide and conquer optimization. 

Shubhojeet Chakraborty:
20180802 05:50:54
very strict time limit..!


kshubham02:
20180722 20:15:48
O(nklogn) with fast i/o gives TLE!! 
Added by:  anupamwadhwa 
Date:  20171110 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Code Rush 2017, IIT (ISM), Dhanbad 