Lottery 2

The Byteotian Lotto company runs number games and cash lotteries. Its most popular product is a lottery called Number Draw. Bajtazar decided to try his luck with it.

A Number Draw coupon has $n$ boxes. In each box you can mark one of the numbers $1$ through $k$. The picture below shows a coupon filled in for $n = 10$ and $k = 3$.

The draw uses a drawing machine that holds $n$ balls of every type $1$ through $k$, so $nk$ balls in total. The top of the machine has $n$ evenly spaced holes, each narrower than a ball. Partway through the draw a pneumatic mechanism starts up and sucks exactly one ball onto each hole. Reading the numbers on those balls from left to right gives a sequence of $n$ numbers, and that sequence is the result of the draw. Everyone whose coupon carries exactly that sequence shares the main prize, a million bytalars. The picture below shows a draw result that would win the main prize for the coupon above.

Bajtazar bought a coupon and marked $n$ numbers on it. Before he handed it in at the outlet, the press reported that the Number Draw is not entirely fair. Balls of the same type, meaning balls carrying the same number, repel each other, so during a draw they never stick to two adjacent holes. The arrangement in the picture above, for instance, cannot happen.

Once he heard this, Bajtazar decided to change some of the $n$ numbers he marked so that no two adjacent numbers are equal. He does not want to push his luck, so he wants to change as few numbers as possible. A box he corrects still has to carry a number between $1$ and $k$. Work out how many numbers Bajtazar has to change.

The first line contains two integers $n$ and $k$ ($2 \le n, k \le 500\,000$).

The second line contains $n$ integers between $1$ and $k$, separated by single spaces. At least one pair of adjacent numbers in this sequence is equal.

Print the smallest number of entries that have to be changed so that no two equal numbers stand next to each other.