Code Submission Evaluation System Login

CSES - HIIT Open 2017

HIIT Open 2017

Contest start:2017-05-27 11:00:00
Contest end:2017-05-27 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard


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?

Input

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.

Output

Print the number of rounds needed to sort the array.

Constraints
Example

Input:
5 3
2 3 4 5 1


Output:
3