题目背景

ちゃんと笑えなきゃね
必须保持笑容才行啊

大した取り柄も無いから
除此之外我一无所有

题目描述

Yuki 是一位魔法少女，她有着 $n$ 块冰，其中第 $i$ 块冰的质量为 $a_i$。

对于所有正整数 $t$：

• 第 $(t-0.5)$ 秒，Yuki 可以对最多 $k$ 块不同的未完全融化（即质量大于 $0$）的冰使用魔法，使它们的质量都增加 $1$；
• 第 $t$ 秒，每块冰都会发生融化，它们的质量都会减少 $1$。

Yuki 需要你求出最大的非负整数 $s$，满足在第 $s$ 秒及第 $s$ 秒前，Yuki 可以使用她的魔法从而使得每块冰都没有完全融化（即满足每块冰的质量始终大于 $0$）。

输入格式

第一行包含两个正整数 $n,k$。

第二行包含 $n$ 个正整数 $a_1,\dots,a_n$。

输出格式

输出一行，包含一个非负整数，表示最大的非负整数 $s$，满足在第 $s$ 秒及第 $s$ 秒前，Yuki 可以使用她的魔法从而使得每块冰都没有完全融化（即满足每块冰的质量始终大于 $0$）。

3 1
3 1 4

2

提示

样例 1 解释

Yuki 可以这样使用魔法：

• 第 $0.5$ 秒时，Yuki 对第 $2$ 块冰使用魔法，此时 $3$ 块冰的质量分别为 $3,2,4$；
• 第 $1$ 秒时，所有冰发生融化，此时 $3$ 块冰的质量分别为 $2,1,3$；
• 第 $1.5$ 秒时，Yuki 对第 $2$ 块冰使用魔法，此时 $3$ 块冰的质量分别为 $2,2,3$；
• 第 $2$ 秒时，所有冰发生融化，此时 $3$ 块冰的质量分别为 $1,1,2$。

容易证明，在第 $3$ 秒时，一定有冰会完全融化，所以最大的满足要求的正整数 $s$ 等于 $2$。

样例 2

见题目附件中的 $\textbf{\textit{ice/ice2.in}}$ 与 $\textbf{\textit{ice/ice2.ans}}$。

该组样例满足测试点 $3$ 的限制。

样例 3

见题目附件中的 $\textbf{\textit{ice/ice3.in}}$ 与 $\textbf{\textit{ice/ice3.ans}}$。

该组样例满足测试点 $5$ 的限制。

样例 4

见题目附件中的 $\textbf{\textit{ice/ice4.in}}$ 与 $\textbf{\textit{ice/ice4.ans}}$。

该组样例满足测试点 $6$ 的限制。

样例 5

见题目附件中的 $\textbf{\textit{ice/ice5.in}}$ 与 $\textbf{\textit{ice/ice5.ans}}$。

该组样例满足测试点 $9$ 的限制。

样例 6

见题目附件中的 $\textbf{\textit{ice/ice6.in}}$ 与 $\textbf{\textit{ice/ice6.ans}}$。

该组样例满足测试点 $10$ 的限制。

数据范围

对于所有测试数据：

• $2 \le n \le 10^6$；
• $1 \le k \le n-1$；
• $1 \le a_i \le 10^6$。

测试点编号	$n\le$	$k\le$	$a_i \le$	特殊性质
$1$	$2$	$1$	$10^6$	否
$2$	$10^3$		$10^3$	是
$3$				否
$4$		$n-1$		是
$5$				否
$6$	$10^6$	$1$	$10^6$	是
$7$				否
$8$		$10$
$9$		$n-1$		是
$10$				否

特殊性质：保证所有冰的质量相等，即 $a_1=a_2=\dots=a_n$。