问题描述

有 $N$ 个城镇位于一条线上，方便地编号为 $1$ 到 $N$。商人高桥要从第 $1$ 个城镇旅行到第 $N$ 个城镇，买卖苹果。

高桥将从第 $1$ 个城镇开始旅行，没有任何苹果。旅行期间可以执行以下操作:

• 移动: 当在第 $i$ 个城镇（$i < N$）时，移动到第 $i + 1$ 个城镇。
• 商品交易: 在当前城镇购买或出售任意数量的苹果。这里假设一个苹果在第 $i$ 个城镇可以以 $A_i$ 日元（日本的货币）购买和出售，其中 $A_i$ 是不同的整数，$1 ≤ i ≤ N$。另外，可以假设他有无限的钱供应。

由于某种原因，在旅行期间对苹果的商品化有限制：整个旅行期间购买和出售的苹果数量之和必须至多为 $T$。（注意，一个苹果可以同时包含在购买和出售的数量中。）

在旅行期间，高桥会执行操作，以使旅行的_利润_最大化。这里，旅行的利润是通过销售苹果而获得的金额，减去购买苹果所花费的金额。请注意，我们对旅行结束时高桥所拥有的苹果不感兴趣。

高桥的商业竞争对手青木想通过操纵苹果的市场价格来给高桥制造麻烦。在高桥开始旅行之前，青木可以将 $A_i$ 更改为另一个任意非负整数 $A_i'$，对于任何城镇 $i$，任意多次。执行此操作的成本为 $|A_i - A_i'|$。执行此操作后，不同的城镇可能具有相等的 $A_i$ 值。

青木的目标是至少降低高桥的预期利润 $1$ 日元。找到实现此目标的最小总成本。可以假设高桥的预期利润最初至少为 $1$ 日元。

约束条件

• $1 ≤ N ≤ 10^5$
• $1 ≤ A_i ≤ 10^9$ （$1 ≤ i ≤ N$）
• $A_i$ 是不同的。
• $2 ≤ T ≤ 10^9$
• 在初始状态下，高桥的预期利润至少为 $1$ 日元。

输入

输入以以下格式从标准输入给出：

$N$ $T$ $A_1$ $A_2$ $...$ $A_N$

输出

打印降低高桥预期利润至少 $1$ 日元的最小总成本。

示例输入 1

3 2
100 50 200

示例输出 1

1

在初始状态下，高桥可以通过以下方式实现最大利润为 $150$ 日元：

1. 从第 $1$ 个城镇移动到第 $2$ 个城镇。
2. 在第 $2$ 个城镇以 $50$ 日元购买一个苹果。
3. 从第 $2$ 个城镇移动到第 $3$ 个城镇。
4. 在第 $3$ 个城镇以 $200$ 日元出售一个苹果。

例如，如果青木将第 $2$ 个城镇的苹果价格从 $50$ 日元更改为 $51$ 日元，高桥将无法实现 $150$ 日元的利润。执行此操作的成本为 $1$，因此答案是 $1$。

降低高桥预期利润的其他方法包括将第 $3$ 个城镇的苹果价格从 $200$ 日元更改为 $199$ 日元。

示例输入 2

5 8
50 30 40 10 20

示例输出 2

2

示例输入 3

10 100
7 10 4 5 9 3 6 8 2 1

示例输出 3

2