Thi lập trình trực tuyến

Một dãy số được gọi là K – không đơn độc nếu mỗi phần tử của dãy đều thuộc một đoạn gồm ít nhất K phần tử liên tiếp có giá trị giống nhau. Ví dụ dãy 1 1 2 2 2 1 1 là 2 – không đơn độc, nhưng không phải là 3 – không đơn độc vì phần tử đầu tiên chỉ thuộc một đoạn gồm 2 số 1. Nếu một dãy số chưa phải là K – không đơn độc, bạn có quyền thực hiện các thao tác biến đổi, mỗi thao tác sẽ cộng ( hoặc trừ ) một đơn vị vào một phần tử của dãy.

Yêu cầu

Hãy đếm số thao tác ít nhất cần thực hiện để biến một dãy số thành dãy K – không đơn độc.

Dữ liệu

• Dòng đầu ghi 2 số N, K. N là số lượng phần tử của dãy số.
• Dòng sau ghi N số tự nhiên thể hiện dãy số.

Kết quả

• Gồm một dòng duy nhất ghi ra số thao tác cần thực hiện.

Ví dụ

Dữ liệu
7 3
2 2 3 4 4 5 5

Kết quả
3

Giới hạn

• 1 ≤ N ≤ 10000
• 1 ≤ K ≤ 100
• K ≤ N
• Phần tử của dãy có giá trị không quá 10⁹

Hạn chế

• Có 30% số test thỏa mãn N ≤ 200.
• Có 50% số test thỏa mãn N ≤ 2000.