说明

史蒂夫有 $N$ 辆矿车，编号从 $1$ 到 $N$，在轨道上从左到右排成一列。最初，第 $i$ 辆矿车中有 $a_i$ 颗宝石。

史蒂夫希望矿车排成一列，使得从左到右每辆矿车中的宝石数量非递减。为此，他计划在所有矿车的右侧修建一条从主轨道分岔出去的侧线。史蒂夫可以将侧线左侧的矿车移入侧线，允许其左侧的其他矿车在主轨道上从它旁边驶过。移入侧线的矿车可以一次一辆地移回主轨道：侧线上的矿车将移回至侧线的左侧，并且位于侧线左侧所有其他矿车的右侧。最后移入侧线的矿车必须是最先移出的矿车：也就是说，侧线遵循后进先出的原则。侧线可以使用任意多次。最后，一旦矿车被移动到侧线的右侧，它就不能再向左移动。以下是从初始位置开始用 5 辆矿车可以进行的移动序列示例：

:::align{center}

:::

史蒂夫有 $K$ 颗备用宝石，他可以将任意数量的备用宝石放入 空 矿车中。史蒂夫尚未修建侧线，他希望限制侧线容量以节省工作量。具有特定容量的侧线最多只能存放相应数量的矿车。例如，如果侧线容量为 1，我们就无法进行上图中的移动，因为那至少需要容量为 2。假设史蒂夫以最优方式将备用宝石放入矿车，那么需要修建的侧线最小容量是多少？

输入格式

输入的第一行包含两个空格分隔的整数 $N$ 和 $K$（$1 \le N \le 3 \times 10^5$，$0 \le K \le 10^{12}$）。

下一行包含 $N$ 个整数 $a_1, \dots, a_n$（$0 \le a_i \le 10^6$），其中第 $i$ 个整数表示第 $i$ 辆矿车中的宝石数量。

输出格式

输出一个整数，在史蒂夫以最优方式将最多 $K$ 颗宝石分配到空矿车中的情况下，需要修建的侧线的最小容量。

4 14
5 0 4 0

1

4 8
5 0 4 0

2

4 123456789
40 30 20 10

3

提示

样例输入 1 的输出解释

一种最优分配是将 6 颗备用宝石放入 2 号矿车，将 7 颗备用宝石放入 4 号矿车。注意这种分配并未使用所有备用宝石。

然后我们可以修建一条容量为 1 的侧线。我们可以按如下步骤将矿车排列成非递减顺序：

1. 将 4 号矿车移动到侧线右侧
2. 将 3 号矿车移入侧线
3. 将 2 号矿车移动到侧线右侧
4. 将 1 号矿车移动到侧线右侧
5. 将 3 号矿车移出侧线
6. 将 3 号矿车移动到侧线右侧

样例输入 2 的输出解释

一种最优分配是将全部 8 颗备用宝石放入 4 号矿车。

然后我们可以修建一条容量为 2 的侧线。我们可以按如下步骤将矿车排列成非递减顺序：

1. 将 4 号矿车移动到侧线右侧
2. 将 3 号矿车移入侧线
3. 将 2 号矿车移入侧线
4. 将 1 号矿车移动到侧线右侧
5. 将 2 号矿车移出侧线
6. 将 3 号矿车移出侧线
7. 将 3 号矿车移动到侧线右侧
8. 将 2 号矿车移动到侧线右侧

样例输入 3 的输出解释

由于没有空矿车，只有一种可能的备用宝石分配方式：不使用任何备用宝石。

然后我们可以修建一条容量为 3 的侧线。我们可以按如下步骤将矿车排列成非递减顺序：

1. 将 4 号矿车移入侧线
2. 将 3 号矿车移入侧线
3. 将 2 号矿车移入侧线
4. 将 1 号矿车移动到侧线右侧
5. 将 2 号矿车移出侧线，然后移动到侧线右侧
6. 将 3 号矿车移出侧线，然后移动到侧线右侧
7. 将 4 号矿车移出侧线，然后移动到侧线右侧

下表展示了 15 分的分布情况：

翻译由 DeepSeek 完成