Description

The annual University of Zagreb student team table tennis tournament will be held next Saturday! Each team consists of $k$ students. $n$ excited students are standing in a queue, waiting to register. Krešo is working at the registration desk. He really does not want to do his job, so he decided not to let the students choose their teams. He decided that the first team will be made up of the first $k$ students in the queue, the second team will be made up of the next $k$ students, the third team will be made up of the next $k$ students, and so on. ($n\equiv 0\pmod k$, so nobody is left over.)

Ante estimates each player's skill with an integer. He wants the first team to have the weakest $k$ players, the second team to have the second weakest $k$ players, and so on, and the last team to have the strongest $k$ players.

Krešo has just taken a break, and Ante decided to rearrange the students in the queue to achieve his goal. He rearranges the students by telling a student to step out of the queue and line up behind another student, or to go to the front of the queue. Moving one student takes one minute. Krešo may come back from his break at any time, so Ante needs to achieve his goal as quickly as possible. Help Ante determine the minimum number of minutes needed to achieve his goal.

Input Format

The first line contains integers $n$ and $k$, satisfying $n\bmod k=0$.

The second line contains $n$ space-separated integers $v_i$, where $v_i$ is the skill level of the $i$-th player standing in the queue.

All contestants have distinct skill levels.

Output Format

Print one line: the minimum number of minutes required to move the students.

4 1
9 12 5 13

1

6 2
16 2 1 7 5 10

1

6 3
7 9 8 3 6 5 

3

Hint

Explanation for Sample 3

Ante should move the students with skill levels $5,6$ and $3$ to the front of the queue, which takes three minutes.

Constraints

• For $30\%$ of the testdata, $1\le n\le 20$.
• For $100\%$ of the testdata, $1\le k\le n\le 5\times 10^3$.

For all valid $v_i$, $1\le v_i\le 10^9$.

Note

This problem is translated from COCI2014-2015 CONTEST #2 T3 STUDENTSKO.

Translated by ChatGPT 5