Ngày hội 26/3 BCH Đoàn trường THPT Chuyên Lào Cai có tổ chức các trò chơi dân gian như: Ô ăn quan, nhảy lò cò, bi… trong đó có trò chơi bi là hấp dẫn học sinh hơn cả. BCH Đoàn trường có \(\mathbf{N}\) viên bi màu được sắp thành một hàng trên mặt đất, mỗi viên bi có một màu thuộc trong số \(\mathbf{K\ (1 \leq K \leq 20)}\) màu được đánh số từ \(\mathbf{1}\) đến \(\mathbf{K}\).

Yêu cầu: Hãy sắp xếp lại các viên bi này sao cho các viên bi cùng màu thì nằm cạnh nhau, sau khi sắp xếp chúng ta sẽ thu được các đoạn liên tiếp gồm những viên bi cùng màu, mỗi màu chỉ thuộc vào đúng một đoạn. Không có 2 đoạn cùng màu mà không nằm cạnh nhau. Mỗi bước chỉ được đổi chỗ hai viên bi cạnh nhau. BCH Đoàn trường yêu cầu hãy sắp xếp lại các viên bi sao cho số bước đổi chỗ thực hiện là nhỏ nhất.

Học sinh nào đưa ra cách giải nhanh nhất và tối ưu nhất sẽ được nhận một phần quà của Đoàn trường, là học sinh trong đội tuyển Tin các em không thể bỏ qua cơ hội nhận phần quà đó, hãy giúp BCH Đoàn trường giải quyết bài toán trên.

Dữ liệu vào: gồm nhiều tests

Mỗi test được mô tả bằng hai dòng:

+ Dòng 1: Ghi hai số nguyên dương 𝑁,𝐾 (2 ≤ 𝑁 ≤ \(\mathbf{10}^{\mathbf{6}}\);1 ≤ 𝐾 ≤ 20)

+ Dòng 2: Ghi 𝑁 số nguyên dương là màu của 𝑁 viên bi theo thứ tự \(1,\ 2,\ ...,\ N\)

Kết thúc tệp dữ liệu vào bằng một dòng ghi hai số 0

Kết quả: Với mỗi test ghi trên một dòng số nguyên là số lần đổi chỗ ít nhất tìm được.

Ví dụ:

Ràng buộc:

Subtask 1: 𝐾 = 2, 𝑁 ≤ 20000 [10% điểm]

Subtask 2: 𝐾 = 3, 𝑁 ≤ 10⁶ [20% điểm]

Subtask 3: 𝐾 ≤ 5, 𝑁 ≤ 20000 [20% điểm]

Subtask 4: 𝐾 ≤ 10, 𝑁 ≤ 10⁶ [30% điểm]

Subtask 5: 𝐾 ≤ 20, 𝑁 ≤ 10⁶ [20% điểm]