Bajtocki Lotek 企业专门从事数字游戏和现金彩票的运营，其中最受欢迎的彩票游戏名为 数字游戏。Bajtazar 也决定尝试一下运气。

数字游戏 的一张彩票包含 $n$ 个位置。在每个位置上可以圈选数字 1 到 $k$ 中的一个。下图展示了在 $n = 10$ 且 $k = 3$ 时的一张示例填好的彩票：

中奖号码的抽取通过一台抽奖机完成，该机器中装有每种数字 1 到 $k$ 各 $n$ 个小球，总共 $nk$ 个球。机器的上部均匀分布着 $n$ 个孔洞，这些孔洞的直径小于球的直径。在某个时刻，抽奖机制会启动一个气动装置，使得每个孔洞吸附一个球。依次读出这些被吸上的球上的数字，就得到一个由 $n$ 个数字组成的序列，作为本次抽奖的结果。在彩票上圈选了与该结果完全一致数字序列的幸运持有者，将获得头奖——一百万 bajtalar 的奖金（平分）。下图展示了一个抽奖结果，此结果正好使上面的彩票赢得头奖。

Bajtazar 购买了彩票，并在上面圈选了 $n$ 个数字。但在他将彩票交到彩票中心之前，媒体爆出内幕，称 数字游戏 的抽奖并不完全公正。研究发现，相同种类的球（即数字相同的球）会相互排斥，因此在抽奖过程中永远不会落在相邻的孔洞里（例如，上图中所示的球的排列就不可能出现）。

得知此事后，Bajtazar 决定修改他圈选的 $n$ 个数字序列，使得序列中没有两个相邻数字是相同的。为了避免节外生枝，他希望尽可能少地修改数字。请你帮助 Bajtazar 计算他最少需要修改多少个数字。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$，满足 $2 \le n, k \le 500,000$。第二行包含一个长度为 $n$ 的数字序列，范围为 {1, ..., $k$}。该序列中至少存在一对相邻的数字相同。

输出格式

输出一行，包含一个正整数，表示为了使序列中没有相邻相同数字，最少需要修改多少个数字。

样例

输入

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

输出

3