1906번 - 자리 바꾸기

내일은 월드생이 팀전을 펼치는 날이다. 팀은 총 K팀으로 나뉘어져 있고, N명의 월드생들은 모두 1팀부터 K팀 중 단 하나의 팀에만 소속되어 있다.

월드생들은 현재 팀에 상관없이 한 줄로 뒤죽박죽으로 앉아서 공부를 하고 있기 때문에 팀끼리 함께 공부하기 위해 자리 교체의 필요성을 느끼고 있다. 하지만 귀찮은 것을 싫어하는 월드생들이기에, 게다가 오늘은 모의고사까지 봤기 때문에 자리를 바꾸는 것을 원치 않는다. 또한, 혼란을 방지하기 위해 서로 자리가 연속하는 사람만 자리를 교체할 수 있다.

결국 이에 자칭 월드 Ace 성원이가 나서서 학생들이 자리를 최소로 바꿔 모든 팀들이 연속적으로 앉는 프로그램을 짜겠다고 나섰다.

첫 번째 줄에 N(1 ≤ N ≤ 300,000)과 K(1 ≤ K ≤ 8)가 입력된다. 이어서 한 줄에 하나씩 N개의 수가 주어지는데 이는 각 학생이 속해 있는 팀의 번호이다.

첫째 줄에 모든 팀이 연속적으로 앉기 위해 필요한 최소의 자리 교체 횟수를 출력한다.

초기 자리 배치 : 2 2 3 2 1 3 1  - 여기서 3번째와 4번째, 5번째와 6번째 앉은 학생들이 서로 자리를 바꾸면

나중 자리 배치 : 2 2 2 3 3 1 1  - 모든 팀이 다 연속적으로 앉게 된다.

물론, 1 1 2 2 2 3 3이나 다르게 앉는 방법도 있겠지만 적어도 2번보다 많은 횟수의 자리 교체가 필요하다.