Problem A
Studentsko
The annual student team competition in table tennis of students enrolled in University of Zagreb takes place next Saturday! Each team consists of $K$ students. The excited students, $N$ of them, are waiting in queue to register.
Krešo works at the registration desk. He doesn’t really feel like doing his job so he decided not to allow students to choose a team. He decided that the first team will consist of the first $K$ students standing in queue, the second team the following $K$ students, the third one the following $K$ students and so on…($N$ will be divisible by $K$ so nobody is left hanging.)
Ante has estimated the skill of each player with an integer. He would like to have the $K$ strongest players in the first team, the following $K$ strongest in the second team and so on…
Krešo has just taken a break and Ante decided to shift the students standing in queue so that he achieves his goal. The way he shifts them is that he tells a student to step out of the queue and go back in queue after another student or to go to the front of the queue. It takes him one minute to do this.
It’s possible that Krešo is going to return from his break any moment so Ante needs to achieve his goal as soon as possible. Help Ante determine the minimal number of minutes necessary for him to achieve his goal.
Input
The first line of input contains the integers $N$ and $K$ ($1 \leq K \leq N \leq 100\, 000)$. The integer $N$ is going to divisible by $K$.
The second line contains $N$ space separated integers $v_ i$ ($1 \leq v_ i \leq 10^9$), the $i$-th number denotes the skill of the $i$-th player standing in queue – lower value means higher skill.
All contestants are going to have distinct levels of skill.
Output
The first and only line of output must contain the minimal required number of minutes.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 1 9 12 5 13 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 2 16 2 1 7 5 10 |
1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
6 3 7 9 8 3 6 5 |
3 |