题目背景
ちゃんと笑えなきゃね / 必须保持笑容才行啊
大した取り柄も無いから / 除此之外我一无所有
题目描述
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$）。
样例 1 输入
3 1 3 1 4
样例 1 输出
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
见题目附件中的 $\textit{ice/ice2.in}$ 与 $\textit{ice/ice2.ans}$。
该组样例满足测试点 $3$ 的限制。
样例 3
见题目附件中的 $\textit{ice/ice3.in}$ 与 $\textit{ice/ice3.ans}$。
该组样例满足测试点 $5$ 的限制。
样例 4
见题目附件中的 $\textit{ice/ice4.in}$ 与 $\textit{ice/ice4.ans}$。
该组样例满足测试点 $6$ 的限制。
样例 5
见题目附件中的 $\textit{ice/ice5.in}$ 与 $\textit{ice/ice5.ans}$。
该组样例满足测试点 $9$ 的限制。
样例 6
见题目附件中的 $\textit{ice/ice6.in}$ 与 $\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$ | $1$ | $10^3$ | 是 |
| $3$ | $10^3$ | $1$ | $10^3$ | 否 |
| $4$ | $10^3$ | $n-1$ | $10^3$ | 是 |
| $5$ | $10^3$ | $n-1$ | $10^3$ | 否 |
| $6$ | $10^6$ | $1$ | $10^6$ | 是 |
| $7$ | $10^6$ | $1$ | $10^6$ | 否 |
| $8$ | $10^6$ | $10$ | $10^6$ | 否 |
| $9$ | $10^6$ | $n-1$ | $10^6$ | 是 |
| $10$ | $10^6$ | $n-1$ | $10^6$ | 否 |
特殊性质：保证所有冰的质量相等，即 $a_1=a_2=\dots=a_n$。