Bạn được cho 1 dãy số \(A\) gồm có \(n\) số tự nhiên và 1 số tự nhiên \(l\) thỏa mãn \(0 \leq l \leq \left \lfloor \frac{n}{2} \right \rfloor\). Bạn được cho thêm 1 dãy số \(B\) cũng có \(n\) số nhưng toàn là số \(0\). Bạn có nhiệm vụ biến đổi dãy \(B\) thành dãy \(A\) theo các bước như sau:

• Bước 1: Chọn 1 vị trí bất kì trên mảng \(B\) sao cho cả bên trái và bên phải vị trí này đều chứa không ít hơn \(l\) phần tử;

• Bước 2: Từ \(2\) vị trí cách vị trí đó \(l\) đơn vị, tăng các phần tử mảng \(B\) trong khoảng đó \(1\) đơn vị.

Lặp lại quy trình \(2\) bước này sao cho thu được mảng \(A\). Các bạn nên biết rằng, nếu như chỉ cần sai \(1\) bước chọn vị trí thì có khi kết quả sẽ sai và không thể sửa chữa lại nữa (vì chỉ có tăng chứ làm gì có chuyện giảm), nên hãy cẩn thận nhé :))

VD: Với dãy A = 1 2 2 1 và \(l = 1\) thì nếu như tăng dãy B = 0 0 0 0 tại 2 vị trí 2 và 3 thì ta sẽ thu được dãy A, tổng cộng cần 2 bước. Quy trình như sau:

0 0 0 0 => 1 1 1 0 => 1 2 2 1.

Input

• Dòng 1 gồm 1 số \(n\) và 1 số \(l\), 2 số cách nhau 1 khoảng trắng;

• Dòng 2 gồm \(n\) số tự nhiên của dãy \(A\), 2 số cách nhau 1 khoảng trắng.

Output

• In ra số bước 2 cần thực hiện để tạo ra mảng \(A\).

\((!!!)\): Test luôn tồn tại 1 cách thực hiện hợp lệ.

Example

4 1
1 2 2 1

2

Constants

• \(n \leq 10^6\)
• \(A_i \leq 10^3\)