#1016. SORT - Sắp xếp lại

Có 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ố màu được đánh số từ đến . Để 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 đầu ghi hai số nguyên dương ;
  • Dòng hai ghi số nguyên dương là màu của viên bi theo thứ tự
  • Kết thúc file dữ liệu bằng một dòng ghi hai số

Dữ liệu ra:

• 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ụ:

Dữ liệu vào:

8 3 
1 1 2 1 2 3 2 3 
5 3 
3 2 1 3 2 
0 0

Dữ liệu ra:

2
3

Giải thích:

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

Giới hạn:

• Có số test tương ứng số điểm có
• Có số test khác tương ứng số điểm có
• Có số test khác tương ứng số điểm có
• Có số test khác tương ứng số điểm có
• Có số test còn lại tương ứng số điểm có