자리 바꾸기

내일은 학생들이 팀전을 치르는 날이다. 전체 학생은 1번부터 K번까지의 팀 중 정확히 하나에 속해 있고, 지금은 팀과 관계없이 한 줄로 섞여 앉아 있다.

같은 팀 학생들이 함께 공부할 수 있도록 자리를 바꾸려 한다. 단, 혼란을 줄이기 위해 한 번의 자리 교체에서는 서로 이웃한 두 학생만 자리를 바꿀 수 있다.

같은 팀 학생들이 모두 연속한 구간에 앉도록 만들 때 필요한 자리 교체 횟수의 최솟값을 구하라. 팀들이 놓이는 순서는 자유롭게 정할 수 있다.

첫째 줄에 학생 수 N과 팀 수 K가 주어진다. (1 <= N <= 300,000, 1 <= K <= 8)

다음 N개의 줄에는 각 학생이 속한 팀 번호가 현재 앉은 순서대로 하나씩 주어진다. 팀 번호는 1 이상 K 이하의 정수이다.

모든 같은 팀 학생들이 각각 연속한 구간에 앉도록 만들기 위해 필요한 최소 자리 교체 횟수를 출력한다.

초기 자리 배치가 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번보다 적은 자리 교체로는 만들 수 없다.