Huawei 正在准备推出其新款超高速移动设备，该设备的相关信息目前处于高度保密状态。为了打造真正快速且可靠的产品，必须在细节上投入大量精力。你现在负责处理一项任务，该任务将影响设备如何选择数据传输频率。

你的新设备可以使用 $n+1$ 种不同的频率，编号从 $0$ 到 $n$。其中频率 $0$ 最适合快速通信，频率 $1$ 次之，以此类推，频率 $n$ 是列表中最不适合的频率。遗憾的是，你不能总是使用频率 $0$。在接下来的 $n$ 秒内，每一秒都有一个频率会因为维护而无法使用。这些频率的索引由整数序列 $a_1, a_2, \dots, a_n$ 提供，其中每个数都在 $0$ 到 $n$ 之间（含 $0$ 和 $n$）。

你的目标是将这 $n$ 秒划分为 $k$ 个周期，每个周期都是一段非空的连续秒数，使得每一秒都恰好属于一个周期。形式化地说，你需要选择整数长度 $l_1, l_2, \dots, l_k$，使得 $\sum_{i=1}^k l_i = n$。那么，在第一个周期内，维护的频率为 $a_1, a_2, \dots, a_{l_1}$；在第二个周期内，维护的频率为 $a_{l_1+1}, a_{l_1+2}, \dots, a_{l_1+l_2}$，依此类推。

在你确定了 $n$ 秒的周期划分后，设备会自动为每个周期选择一个频率，该频率为该周期内任何一秒都可用的最小频率 $x$，即满足 $x \ge 0$ 且对于该周期内的任意 $i$ 都有 $x \neq a_i$ 的最小整数 $x$。记这些周期选择的频率为 $f_1, f_2, \dots, f_k$。注意，这些频率是自动选择的，你唯一能影响此过程的方式就是改变周期的划分方式。

为了保障用户安全，你需要为所有周期选择一个紧急频率 $y$。作为紧急频率，它不会受到任何维护的影响，因此 $y$ 可以等于任何 $a_i$，但它不能与任何 $f_i$ 相等。可以证明，总是至少存在一个有效的 $y$ 可供选择。当然，你会选择满足条件的最小 $y$ 作为紧急频率。

本题的目标是划分 $n$ 秒为 $k$ 个周期，使得紧急频率尽可能小。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($1 \le k \le n \le 1\,000\,000$)，分别表示序列 $a$ 的长度和周期的数量。

第二行包含序列 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le n$)。

输出格式

输出一个整数，表示通过将输入序列划分为恰好 $k$ 个周期所能获得的最小紧急频率。

样例

样例输入 1

2 2
0 2

样例输出 1

2

样例输入 2

3 1
2 1 1

样例输出 2

1

样例输入 3

3 2
1 3 0

样例输出 3

2