Cyclic Buffer Shifting

We are given a cyclic buffer of size \( n \) containing a permutation \( a_1,a_2,\ldots,a_n \) of the integers \(1,2,\ldots,n\). Only the first \( k \) positions of the buffer are visible (they have "readers").

We want to "visit" the integers from \(1\) to \( n \) in increasing order. An integer can be visited only if at the time of the visit it is located in one of the first \( k \) positions of the buffer. At any moment we can shift the entire buffer any number of times in either direction. The operations are:

• Left shift: the integer at position \(1\) moves to position \(n\) and every other integer at position \( i \) moves to position \( i-1 \) (for \( i>1 \)).
• Right shift: the integer at position \( n \) moves to position \(1\) and every other integer at position \( i \) moves to position \( i+1 \) (for \( i<n \)).

Let the current configuration be represented by an offset \( t \) (with \( 1\le t\le n \)) so that the integer originally at position \( i \) will appear at position \[ \text{newPos}(i) = \begin{cases} i-t+1,& \text{if } i \ge t,\\ i-t+n+1, & \text{if } i < t, \end{cases} \] and an integer \( x \) can be visited if its new position \( \le k \). Initially \( t=1 \) (i.e. no shift) and the cost is the total number of individual shift operations.

The task is to compute the minimum number of shifts required so that we can visit all integers \(1,2,\ldots, n\) in order. You are allowed to shift the buffer arbitrarily between visits.

The mathematical condition for visiting the integer \( i \), whose initial position is \( p_i \), given current state \( t \) (with 1-indexing) is \[ \left(((p_i - t + n) \bmod n) + 1\right) \le k. \]

Input and output format details are given below.

inputFormat

The first line contains two integers \( n \) and \( k \) \((1 \le k \le n)\). The second line contains \( n \) distinct integers \( a_1,a_2,\ldots,a_n \), which form a permutation of \( \{1,2,\ldots,n\} \).

outputFormat

Output a single integer: the minimum number of shifts (each left or right shift counts as one operation) needed so that we can visit every integer from \(1\) to \( n \) in increasing order.

sample

5 2
3 1 4 5 2

3