题目描述

给你一个长度为 $n$ 的整数数列 $a_1, a_2, \ldots, a_n$。

数列中的每个元素都在 $1$ 到 $x$ 范围内。这也就是说，对于任意 $1 \le i \le n$，均有 $1 \le a_i \le x$。

你可以对这个数列进行任意次如下操作：

选择一个不包含整数 $k$ 的区间 $[l, r]$，并将这个区间里的每个元素的数值都更新为 $k$。

其中：$1 \le l \le r \le n$，$1 \le k \le x$。

也就是说，首先你要选择的区间 $[l, r]$ 内不能存在数值为 $k$ 的元素，即：对于任意 $l \le i \le r$，均满足 $a_i \neq k$；然后，你需要将满足 $l \le i \le r$ 的 $a_i$ 都更新为 $k$。$k$ 只能是 $1$ 到 $x$ 范围内的某一个整数。

问：最少需要几次操作能使数列 $a$ 中的所有数的数值相同（即 $a_1 = a_2 = \ldots = a_n$）？

输入格式

第一行，两个整数 $n$ 和 $x$，以空格分隔（$1 \le x \le n \le 100$）。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$，两两之间以一个空格分隔（$1 \le a_i \le x$）。

输出格式

输出一个整数，表示使数列 $a$ 所有数的数值相同所需的最少操作次数。

样例

3 2
1 2 1

1

6 3
1 2 3 1 2 3

2

12 3
3 1 3 1 2 1 1 2 3 1 1 3

2

说明/提示

样例解释

样例 1 的一种最优解：将区间 $[2, 2]$ 更新为 $1$。

样例 2 的一种最优解：先将区间 $[1, 2]$ 更新为 $3$，再将区间 $[4, 5]$ 更新为 $3$。

样例 3 的一种最优解：先将区间 $[4, 8]$ 更新为 $3$，再将区间 $[1, 12]$ 更新为 $2$。

数据规模与约定

• 对于 $50\%$ 的数据，$n \le 10$
• 对于 $100\%$ 的数据，$1 \le x \le n \le 100$，$1 \le a_i \le x$