CSES - HIIT Open 2017 - Jonnesort
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Jonnesort is a new sorting algorithm that resembles the famous bubble sort algorithm. The algorithm is given an array of n elements and a parameter k where 2 \le k \le n, and the algorithm sorts the array.

The algorithm consists of one or more rounds. On each round, the algorithm goes through the array from left to right and sorts each subarray of size k. The algorithm terminates when the array does not change during a round. Note that if k=2, the algorithm works like the standard bubble sort algorithm.

Your task is to study the efficiency of Jonnesort. How many rounds does the algorithm need to sort an array?


The first input line contains two integers n and k: the size of the array and the parameter k.

The second line contains n integers a_1,a_2,\ldots,a_n: the contents of the array.


Print the number of rounds needed to sort the array.


  • 2 \le k \le n \le 1000
  • 1 \le a_i \le 10^9



5 3
2 3 4 5 1