题目描述

有 $N$ 个城镇排成一条直线。行商人高桥君从城镇 $1$ 出发，一边买卖苹果一边前往城镇 $N$。

一开始，高桥君在城镇 $1$，手中没有任何苹果。高桥君可以重复进行以下任意操作：

• 移动：当他在城镇 $i$（$i < N$）时，可以移动到城镇 $i+1$。
• 苹果买卖：可以在任意城镇 $i$（$1 \leq i \leq N$）以 $A_i$ 日元的价格任意买入或卖出任意数量的苹果。这里 $A_i$ 是互不相同的整数。

在一个城镇中买卖苹果的数量没有限制，但整个旅途中买卖苹果的总数（买入和卖出的总和）不能超过 $T$ 个。

高桥君会选择使旅途利润（即卖出苹果所得总金额减去买入苹果所花总金额）最大的方式进行旅途。旅途结束时手中剩余苹果的价值不计入利润，只考虑买卖过程中产生的金额。

在旅途开始前，青木君可以对任意城镇 $i$ 的 $A_i$ 修改为任意非负整数 $A_i'$，每进行一次这样的操作需要支付 $|A_i - A_i'|$ 的代价。操作后，不同城镇之间苹果价格可以相同。

青木君的目标是用尽可能小的总代价，使高桥君的最大利润至少减少 $1$ 日元。请你求出所需总代价的最小值。

可以假设在初始状态下，高桥君一定可以获得至少 $1$ 日元的利润。

输入格式

输入以如下格式从标准输入读入：

$N$ $T$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出使高桥君的利润至少减少 $1$ 日元所需的总代价的最小值。

样例 1

输入

3 2
100 50 200

输出

1

样例 2

输入

5 8
50 30 40 10 20

输出

2

样例 3

输入

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$
• 保证输入情况下高桥君可以获得至少 $1$ 日元的利润

样例解释 1

在该输入情况下，高桥君可以通过以下方式获得最大利润 $150$ 日元：

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

例如，如果青木君将城镇 $2$ 的苹果价格从 $50$ 日元改为 $51$ 日元，高桥君无论如何都无法获得 $150$ 日元的利润。也就是说，只需花费 $1$ 的代价就能使高桥君的利润至少减少 $1$ 日元，因此答案为 $1$。同样地，将城镇 $3$ 的苹果价格从 $200$ 日元改为 $199$ 日元，也可以以 $1$ 的代价达到目的。

由 ChatGPT 4.1 翻译