Lannister Army

Statement

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

First line of input contain two integers N and K. Second line of input contain N number of integers, ith of which denote height of ith warrior standing in that single row (represented as H[i]).

Constraints

  • 1 ≤ N ≤ 5000
  • 1 ≤ K ≤ N
  • 1 ≤ H[i] ≤ 105

Output

Output the minimum possible value of "total unhappiness".

Example input 1
6 3
20 50 30 60 40 100
	
Example output 1
0
	
Explanation 1

Break as :
Row 1 : 20 50
Row 2 : 30 60
Row 3 : 40 100

Example input 2
8 3
20 50 30 60 40 100 5 1
	
Example output 2
2
	
Explanation 2

Row 1 : 20 50 30 60, Unhappiness = 1
Row 2 : 40 100, Unhappiness = 0
Row 3 : 5 1, Unhappiness = 1
Total = 2

Time and memory limit:

  • 2 seconds
  • 256MB

Problem source: SPOJ