Problem Description

The annual table tennis team tournament for students at the University of Zagreb is scheduled for next Saturday! Each team consists of $k$ students. $n$ excited students are queuing up for registration. Krešo is working at the registration desk. He really doesn't want to do his job, so he decides not to let the students choose their teams. He decides that the first team will consist of the first $k$ students in the queue, the second team will consist of the next $k$ students, the third team will consist of the following $k$ students, and so on. (Since $n \equiv 0 \pmod{k}$, no one is left out.)

Ante estimates the skill of each player 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, with the last team having the strongest $k$ players.

Krešo just took a break, and Ante decides to rearrange the students in the queue to achieve his goal. He rearranges students by telling a student to step out of the queue and either get in line behind another student or move to the front of the queue. Each such move takes one minute. Krešo could return 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 required to achieve his goal.

Input Format

The first line of input contains the integers $n$ and $k$, where $n \bmod k = 0$.

The second line contains $n$ space-separated integers $v_i$, representing the skill levels of the players in the queue.

All participants have different skill levels.

Output Format

Output a single line containing the minimum number of minutes required to rearrange the students.

Sample Input and Output

Sample Input #1

4 1
9 12 5 13

Sample Output #1

1

Sample Input #2

6 2
16 2 1 7 5 10

Sample Output #2

1

Sample Input #3

6 3
7 9 8 3 6 5

Sample Output #3

3

Notes

Sample 3 Explanation

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

Data Range and Constraints

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

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

Notes

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

见题面 Input 部分

见题面 Output 部分