The Bajtocki Lotek company specializes in conducting number games and cash lotteries, among which the most popular is the lottery called Number Game. Bajtazar has also decided to try his luck in the game.

A coupon for the Number Game contains $n$ positions. In each of them, one can mark one of the numbers $1, \dots, k$. The figure below shows an example of a filled-out coupon for $n = 10$ and $k = 3$:

The drawing of winners is conducted using a lottery machine containing $n$ balls of each type $1, \dots, k$, giving a total of $nk$ balls. In the upper part of the machine, $n$ holes are evenly spaced, each with a diameter smaller than the diameter of a ball. At a certain moment during the draw, a pneumatic mechanism is activated, causing one ball to be sucked into each hole. By listing the numbers on the drawn balls in order, a sequence of $n$ numbers is obtained, which constitutes the result of the draw. The lucky owners of coupons on which exactly this sequence of numbers was marked win the grand prize - one million bajtalars to be shared. The figure below shows the result of a draw for which the above coupon would win the grand prize.

Bajtazar purchased a coupon and marked $n$ numbers on it. However, before he could submit his coupon at the collection point, a leak appeared in the media that the draw in the Number Game is not entirely fair. It was discovered that balls of the same type—that is, with the same number—repel each other and will never be positioned at adjacent holes during the draw (e.g., the arrangement of balls shown in the figure above would not be possible).

Upon learning this, Bajtazar decided to change the sequence of $n$ numbers he indicated so that no two consecutive numbers in the sequence are the same. To avoid tempting fate, he would like to change as few numbers in his sequence as possible. Help Bajtazar determine how many numbers he must change.

Input

The first line of input contains two integers $n$ and $k$ ($2 \le n, k \le 500\,000$). The second line contains a sequence of $n$ numbers in the range $\{1, \dots, k\}$. The sequence contains at least one pair of adjacent identical numbers.

Output

The first and only line of output should contain a single positive integer - the minimum number of elements in the sequence that must be changed so that no two identical numbers appear next to each other.

Examples

Input 1

10 3
2 1 1 3 2 2 1 1 1 3

Output 1

3