说明

本题使用了Special Judge来Y(^_^)Y

Sepcial Judge Module By stong9070

背景

stong9070者，三国M国之谋士也，忽生异志，舍策士之业，欲助山间贫童习书，然乏资财，遂欲为商贾以致富。

题目描述

有$N$个城镇位于一条线上，编号为1到$N$，商人stong9070从1号城镇前往N号城镇旅游，同时想买卖苹果赚取旅游费用和资助山区儿童的资金。

stong9070将在没有苹果的情况下从1号城镇开始旅行。旅行过程中可以执行的操作如下：

• move:当在城镇$i(i＜N)$时，移动到城镇$i$+1
• merchandise: 在当前城镇购买或出售任意数量的苹果。这里，假设一个苹果总是可以在城镇$i(1≤i≤N)$以$A_i$的价格买卖，其中$A_i$是不同的整数。此外，假设有无限的金钱供应。

出于某种原因，在旅行期间推销苹果数量是有限制的：在整个旅行期间购买的苹果数量和出售的苹果数量之和最多只能是$T$(注意，一个苹果买与卖均算一次)

在旅行期间，stong9070将展示他的商业天赋，使旅行的利润最大化。在这里，旅行的利润是卖苹果赚的钱(卖苹果获得的钱减去买苹果花的钱)。请注意，stong9070对旅行结束时拥有的苹果数量不感兴趣。

stong9070的商业竞争对手冷亦萧想通过操纵苹果的市场价格来制造麻烦。在stong9070旅行开始之前，冷亦萧可以多次将任意城镇$i$的$A_i$变为另一个任意的非负整数$A_{i'}$。执行此操作的成本为 |$A_i−A_{i′}$|。执行此操作后，不同的城镇可能具有相等的$A_i$值。

冷亦萧的目标是将stong9070的预期利润至少减少1元。找到实现这一目标的最低总成本。你可以假设stong9070的预期利润最初至少是1元。

输入格式

第一行两个整数$N,T$

第二行$N$个整数$A_i$，$A_i$各不相同

输出格式

输出冷亦萧最低总成本，使stong9070的预期利润至少减少1元。

样例

3 2
100 50 200

1

样例解释

在初始状态下，stong9070可以实现的最大利润150元，如下：

• 1、从城镇1旅游到城镇2
• 2、在城镇2花50元买一个苹果
• 3、从城镇2旅游到城镇3
• 4、在城镇3以200元卖一个苹果

例如，冷亦萧在城镇2把苹果的价格从50元改变至51元，stong9070将无法实现的利润150元。执行此操作的成本为1，因此答案是1。

冷亦萧还有其他方法可以降低stong9070的预期利润，比如在城镇3把苹果的价格从200元改变至199元。

5 8
50 30 40 10 20

2

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

2

数据范围

• $1\leq N \leq 10^5$
• $1 \leq A _i \leq 10^9(1 \leq i \leq N)$
• $A _i$ 各不相同
• $2 \leq T \leq 10^9$
• 在最初的状态下，stong9070的预期利润至少为1元