Description

精灵糖果店的货架上排列着 $k$ 种魔法糖果盒（编号 $1$~$k$），每种盒子只能存放对应类型（即盒子编号）的糖果。

今天，糖果精灵需要将 $n$ 颗糖果按顺序放入盒中------第 $i$ 颗糖果的类型 $a_i$。但有一个特殊规则：

魔法盖的约束：货架上始终有一个魔法盖，必须盖在某个非空盒子上（初始可任选位置）

触发移动的条件：当需要往被盖子覆盖的盒子放入糖果时，必须先将盖子移到其他盒子上

糖果精灵想要以最少的盖子移动次数完成所有糖果的存放。你能找到这个最小值吗？

Format

Input

第一行两个整数$n$,$k$（$2 \leq k \leq 10^9$ , $1 \leq n \leq 10^6$）

第二行 $n$ 个整数 $a_1$...$a_n$，表示糖果类型序列

Output

输出一个整数，表示最少移动次数

Samples

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

2

2 2
1 2

1

Limitation

1s, 256KiB for each test case.