Minimum Moves to Arrange Table Tennis Teams

It is time for the annual Zagreb University table tennis team competition next Saturday! Each team consists of \(k\) players. There are \(n\) excited students lined up for registration. Krešo, who works at the registration desk, decides to form teams in a lazy way: the first team will consist of the first \(k\) students in line, the second team the next \(k\) students, the third team the following \(k\) students, and so on (since \(n\equiv 0\pmod{k}\), no one is left over).

However, Ante estimates each player’s skill with an integer and wishes the teams to be arranged so that the first team has the weakest \(k\) players, the second team has the next weakest \(k\) players, and so on, with the last team having the strongest \(k\) players.

While Krešo is on a break, Ante decides to rearrange the queue to achieve his goal. The only operation allowed is to call a single student to step out of the current queue and insert him either at the very front or immediately after some other student. Each such move takes one minute. Since Krešo might return at any time, Ante must accomplish his goal as quickly as possible. Determine the minimum number of minutes required to rearrange the queue.

Note: The final arrangement must be such that when the queue is divided into consecutive groups of \(k\) players, the set of skills in the first group equals the \(k\) smallest skills, the set in the second group equals the next \(k\) smallest skills, and so on. The order of players within a team does not matter.

inputFormat

The first line contains two integers \(n\) and \(k\) (\(1 \leq k \leq n\), and \(n\) is divisible by \(k\)).

The second line contains \(n\) integers representing each student’s skill level. All skill levels are assumed to be distinct.

outputFormat

Output a single integer representing the minimum number of minutes required to achieve the desired arrangement.

sample

6 3
1 2 3 4 5 6

0