Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QBSORT - Sắp xếp các viên bi

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/qbsort


Có N viên bi màu được sắp thành một hàng trên mặt đất, các viên bi thuộc 1 trong K màu được đánh số từ 1 đến K.

Để tiện phân loại, beo_chay_so 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 beo_chay_so 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 đúng 1 đoạn.

Mỗi lần beo_chay_so chỉ được đổi chỗ 2 viên bi cạnh nhau, hãy giúp beo_chay_so sắp xếp lại các viên bi này sao cho số lần phải đổi chỗ các viên bi là ít nhất.

Input

Dòng thứ nhất ghi 2 số N và K là số viên bi và số màu. ( 2 ≤ N ≤ 20000, 1 ≤ K ≤ 10 )

Dòng thứ hai ghi N số nguyên dương là màu của N viên bi theo thứ tự.

Output

Ghi ra duy nhất một số nguyên là số phép đổi chỗ ít nhất.

Example

Input:
5 3
3 2 1 3 2

Output:
3

Giải thích:
Đổi chỗ số thứ 3 và 4:
3 2 3 1 2
Đổi chỗ số thứ 4 và 5:
3 2 3 2 1
Đổi chỗ số thứ 2 và 3:
3 3 2 2 1

Được gửi lên bởi:special_one
Ngày:2008-10-18
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2017-08-27 04:48:17
boobssort AC nhé
độ phức tạp O(boobs*n)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.