## COCI '14 Contest 2 #3 Studentsko

View as PDF

Points: 12 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem types

The annual student team competition in table tennis of students enrolled in University of Zagreb takes place next Saturday! Each team consists of students. The excited students, 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 students standing in queue, the second team the following students, the third one the following students and so on… ( will be divisible by so nobody is left hanging.)

Ante has estimated the skill of each player with an integer. He would like to have the strongest players in the first team, the following 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 Specification

The first line of input contains the integers and . The integer is going to be divisible by .
The second line contains space separated integers , number denotes the skill of the player standing in queue.

All contestants are going to have distinct levels of skill.

#### Output Specification

The first and only line of output must contain the minimal required number of minutes.

#### Scoring

In test cases worth 30% of total points, it will hold .

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

#### Explanation of Output for Sample Input 3

Ante should move the students with skill levels 5, 6 and 3 to the front of the queue. It takes him three minutes to do that.