题目描述

有 $N$ 辆矿车从左到右排成一行，编号为 $1,2,\ldots,N$。初始时，第 $i$ 辆矿车中有 $a_i$ 颗宝石。

所有矿车都要沿主轨向右移动。主轨右端连接着一条支轨：

• 当一辆矿车到达岔口时，可以让它沿主轨驶到支轨右侧，也可以暂时把它移入支轨；
• 支轨中的矿车可以一次一辆移回主轨。移回的矿车位于岔口左侧，并且位于所有尚未到达岔口的矿车的右侧；
• 支轨满足后进先出规则：最后进入支轨的矿车必须最先移出；
• 一辆矿车一旦驶到支轨右侧，就不能再回到左侧。

所有矿车都驶到支轨右侧后，从左到右构成最终排列。你希望最终排列中每辆矿车的宝石数不下降。

若支轨容量为 $D$，则任意时刻支轨中最多同时存放 $D$ 辆矿车。

此外，你有 $K$ 颗备用宝石。在开始移动矿车之前，你可以把备用宝石放入初始时为空的矿车，也就是满足 $a_i=0$ 的矿车中：

• 每辆初始为空的矿车可以放入任意非负整数颗宝石；
• 初始不为空的矿车不能再加入宝石；
• 备用宝石不必全部用完。

在最优分配备用宝石的前提下，请求出使矿车能够重排为宝石数不下降的顺序时，支轨所需的最小容量。

特别地，若不使用支轨就能达到要求，答案为 $0$。

输入格式

第一行包含两个整数 $N,K$。

第二行包含 $N$ 个整数 $a_1,a_2,\ldots,a_N$。

输出格式

输出一个整数，表示所需支轨容量的最小值。

样例

样例输入 1

4 14
5 0 4 0

样例输出 1

1

样例输入 2

4 8
5 0 4 0

样例输出 2

2

样例输入 3

4 123456789
40 30 20 10

样例输出 3

3

样例解释

对于样例 1，一种最优方案是给第 $2$ 辆矿车加入 $6$ 颗宝石，给第 $4$ 辆矿车加入 $7$ 颗宝石，得到序列 $5,6,4,7$。此时容量为 $1$ 的支轨足以完成重排。

对于样例 2，一种最优方案是把 $8$ 颗备用宝石全部放入第 $4$ 辆矿车，得到序列 $5,0,4,8$。此时最小容量为 $2$。

对于样例 3，没有空矿车可以加入备用宝石。要把 $40,30,20,10$ 重排为不下降顺序，最小容量为 $3$。

数据范围

对于所有测试数据，满足：

• $1\le N\le 3\times 10^5$；
• $0\le K\le 10^{12}$；
• $0\le a_i\le 10^6$；
• 所有输入均为整数。

子任务