Problem
汤姆索亚说服了他的几个朋友帮助他完成粉刷波莉姨妈房子周围围栏的艰巨任务。栅栏由 k 个连续的木板组成，编号从 1 到 k，第 k 个木板之后是第一个木板。
汤姆的朋友们非常挑剔，第 i 个朋友只有在允许他画正好是 ai 个连续棋盘的一段时才同意参与绘画。汤姆只有一把画笔，所以他的朋友们会轮流画完分配给他们的整个部分。汤姆唯一要做的就是选择邀请他的朋友的顺序，以及为每个人选择所需的连续板数。
与此同时，汤姆的每个朋友都准备好为未上漆的栅栏板和他的一位前任已经上漆的板子上漆。然而，朋友们在未上漆的木板上上漆会获得更多乐趣。汤姆想选择一个数字 x 并分配要涂漆的栅栏部分，使他的每个朋友至少涂漆 x 块未涂漆的木板。 Tom 非常爱他的朋友，希望他们每个人都能从粉刷围栏中获得最大收益，所以他试图最大化 x。
帮助汤姆了解他能给他的朋友带来多少快乐。
输入数据格式
输入文件的第一行包含两个整数 n (1 ≤ n ≤ 10
5 ) 和 k (1 ≤ k ≤ 10
9 )。下一行包含 n 个整数——值 a
i (1 ≤ a
i ≤ k).
输出数据格式
打印一个数字——
x 的最大可能值。
<正文>
| 输入 |
输出 |
2 100
5 10
| 5 |
4 10
7 8 3 5
| 2 |
说明
在第一个例子中 x = 5 因为其中一个朋友不想画超过五块板。他会先来，画他的五块板，然后再将另外 10 块未上漆的板交给汤姆的第二个朋友。剩下的 85 块木板必须由 Tom 自己绘制。
在第二个例子中，可以达到x = 2，例如，像这样。首先，第三个朋友画板 4 到 6（3 个未上漆的板）。然后第四个朋友画板 1 到 5（3 个未上漆的板）。然后第二个朋友画板 1 到 8（2 个未上漆的板）。最后，第一个朋友画板 6 到 10 和 1 到 2（2 个未上漆的板，注意栅栏是循环的，这些板形成连续的段）。