복권 2

바이트나라 복권 회사는 숫자 게임과 현금 복권을 운영한다. 그중 가장 인기가 많은 상품은 숫자 뽑기라는 복권이다. 바이타자르도 이 복권으로 운을 시험해 보기로 했다.

숫자 뽑기 응모권에는 칸이 $n$개 있다. 각 칸에는 $1$부터 $k$까지의 수 중 하나를 표시할 수 있다. 아래 그림은 $n = 10$, $k = 3$일 때 응모권을 채운 예다.

추첨은 추첨기로 한다. 추첨기 안에는 $1$번부터 $k$번까지 각 종류의 공이 $n$개씩, 모두 $nk$개 들어 있다. 추첨기 윗면에는 공의 지름보다 작은 구멍이 $n$개 일정한 간격으로 뚫려 있다. 추첨 도중 공압 장치가 켜지면 구멍마다 공이 하나씩 빨려 붙는다. 붙은 공에 적힌 수를 순서대로 적으면 길이가 $n$인 수열이 나오고, 이 수열이 추첨 결과다. 응모권에 이 수열을 그대로 표시한 사람은 1등 상금인 100만 바이트탈라를 나눠 갖는다. 아래 그림은 위 응모권이 1등에 당첨되는 추첨 결과다.

바이타자르는 응모권을 사서 수 $n$개를 표시했다. 그런데 판매점에 응모권을 내기 전에 숫자 뽑기 추첨이 공정하지 않다는 제보가 언론에 나왔다. 같은 종류의 공, 즉 같은 수가 적힌 공끼리는 서로 밀어내기 때문에 추첨 중에 이웃한 두 구멍에 나란히 붙는 일이 없다는 것이다. 예를 들어 위 그림과 같은 배치는 나올 수 없다.

이 사실을 안 바이타자르는 자신이 표시한 수 $n$개 중 몇 개를 고쳐서 이웃한 두 수가 같지 않게 만들기로 했다. 괜히 운을 시험하고 싶지는 않으니 고치는 수의 개수는 최대한 적게 하려고 한다. 고친 칸에도 $1$ 이상 $k$ 이하의 수만 표시할 수 있다. 바이타자르가 수를 몇 개 고쳐야 하는지 구하시오.

첫째 줄에 정수 $n$과 $k$가 주어진다. ($2 \le n, k \le 500\,000$)

둘째 줄에 $1$ 이상 $k$ 이하인 정수 $n$개가 빈 칸을 사이에 두고 주어진다. 이 수열에는 같은 수가 이웃해 있는 자리가 적어도 한 군데 있다.

첫째 줄에 이웃한 두 수가 같지 않도록 만들기 위해 고쳐야 하는 수의 최소 개수를 출력한다.