Sắp xếp lại (rsort.*)

Có \(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ố \(k\) màu được đánh số từ 1 đến \(k\). Để tiện phân loại, Cuội muốn 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, như vậy Cuội 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. Mỗi bước, Cuội chỉ được đổi chỗ hai viên bi cạnh nhau.

Yêu cầu: Hãy giúp Cuội 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.

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 \(n,k\ (2\ \leq \ n\ \leq \ 10^{6};1\ \leq \ k\ \leq \ 20)\);

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

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

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

Ví dụ:

Input	Output
8 3 1 1 2 1 2 3 2 3 5 3 3 2 1 3 2 0 0	2 3

Giải thích: Trong trường hợp thứ nhất cần sắp xếp lại thành 1 1 1 2 2 2 3 3 với 2 phép đổi chỗ (lần lượt: vị trí 3 đổi chỗ cho vị trí 4, vị trí 6 đổi chỗ cho vị trí 7) . Trong trường hợp thứ hai cần sắp xếp lại thành 3 3 2 2 1 với 3 phép đổi chỗ (lần lượt: vị trí 3 đổi chỗ cho vị trí 4; vị trí 4 đổi chỗ cho vị trí 5; vị trí 2 đổi chỗ cho vị trí 3)

Ràng buộc:

+ Có 10% số test tương ứng 10% số điểm có \(k\ = \ 2;\ n\ \leq \ 20000\)

+ Có 20% số test tương ứng 20% số điểm có \(k\ = \ 3;\ n\ \leq \ 10^{6}\ \ \)

+ Có 20% số test tương ứng 20% số điểm có \(k\ \leq \ 5;\ n\ \leq \ 20000\)

+ Có 30% số test tương ứng 30% số điểm có \(k\ \leq \ 10;\ n\ \leq \ 10^{6}\ \)

+ Có 20% số test tương ứng 20% số điểm có \(k\ \leq \ 20;n\ \leq \ 10^{6}\)