解题思路

设答案为 $x$，那么题目要求把数组划分成恰好 $k$ 个连续子数组，并且每一段的 $\mathrm{MEX}\ge x$。

因为一个数组的 $\mathrm{MEX}\ge x$，等价于这个数组中至少都出现过 $0,1,2,\dots,x-1$。 所以问题就变成了：

是否能够把原数组划分出至少 $k$ 段，使得每一段都包含 $0\sim x-1$ 这 $x$ 个数。

题目内容

给定一个长度为 $n$ 的数组 $a$ 和一个整数 $k$ 。需要将整个数组划分成恰好 $k$ 个连续子数组，每个子数组至少包含一个元素。

对一个数组 $v$ ，$MEX(v)$ 表示没有出现在其中的最小非负整数。在所有可能的划分中，定义

$x=\min _{i=1}^{k} \operatorname{MEX}\left(b_{i}\right),$

其中 $b_1,b_2,...,b_k$ 为划分得到的子数组。你的任务是 使$x$尽量大，并求出能达到的最大值。

定义一个数组的 $MEX$ 为：$MEX(b_i)$ 指在数组 $b$ 中没有出现过的最小非负整数。例如：$MEX([0,2,1])=3,MEX([1,2,3])=0，MEX([0,1,1,0])=2$

输入描述

第一行包含两个整数 $n，k(1≤k≤n≤2×10^5)$，表示数组长度和要划分的子数组个数；

第二行包含 $n$ 个整数 $a_1,a_2,...,a_n(0≤a_i≤10^9)$ ，表示数组的元素。

输出描述

输出一行，一个整数，表示在某种将数组划分成 $k$ 个子数组的方式下，最大可能值 $x$.

样例1

输入

6 2
0 0 1 1 2 2

输出

1