Mô tả và yêu cầu

Sắp xếp sách
Tên file chương trình SAPXEP.*
Hiện tại kệ sách của Khoa đang có 𝑛 quyển sách được đánh số thứ tự từ 1 đến 𝑛 theo
thứ tự từ đầu đến cuối kệ, quyển sách thứ 𝑖 thuộc thể loại 𝑎𝑖. Khoa đang muốn sắp xếp các
quyển sách này lại sao cho các quyển có cùng thể loại nằm cạnh nhau. Việc sắp xếp các
quyển sách này được tiến hành bằng nhiều lần di chuyển, mỗi lần Khoa có thể chọn một
quyển sách bất kỳ và di chuyển nó về vị trí cuối cùng của kệ sách, các quyển khác sẽ được
dồn lại gần nhau.
Hãy lập trình xác định số lần di chuyển ít nhất để Khoa có thể sắp xếp các quyển sách
này lại theo mình mong muốn.
Dữ liệu vào: cho trong file văn bản SAPXEP.INP có cấu trúc như sau:
 Dòng đầu ghi số nguyên dương 𝑛 (𝑛 ≤ 105).

 Dòng thứ hai ghi 𝑛 số nguyên dương, số thứ 𝑖 cho biết giá trị 𝑎𝑖 (𝑎𝑖 ≤ 𝑛).
Kết quả: ghi ra file văn bản SAPXEP.OUT một số là kết quả tìm được.

Ví dụ

SAPXEP.INP                       SAPXEP.OUT
                      5                                2
                      2 1 1 2 3
Giải thích ví dụ:
      Lần 1:        2      1     1      2     3                          2     1      2     3      1

      Lần 2:        2      1     2      3     1                          2     2      3     1      1
Ràng buộc:
       60% số test có 𝑛     ≤  103 và các giá trị 𝑎𝑖    ≤  2.

       20% số test có 𝑛     =  10 và các giá trị 𝑎𝑖   ≤  5.
       20% số test không ràng buộc gì thêm.