分数: 400 点
问题陈述
有 N 城镇位于一条线上,编号方便 1 通过 N。商人高桥正从城镇出发旅行 1 到镇 N,买卖苹果。
高桥将开始城镇旅行 1,他没有苹果。旅行期间可以执行的操作如下:
- 移动:在城镇时 i (i < N),搬到城镇 i + 1.
- 商品:在当前城镇购买或出售任意数量的苹果。这里,假设一个苹果总是可以以 A_i 日元(日本货币)在镇上 i (1 ≦ i ≦ N),其中 A_i 是不同的整数。另外,你可以假设他有无限的货币供应。
由于某种原因,旅行期间销售苹果有一个限制:整个旅行期间购买的苹果数量和出售的苹果数量之和最多不得超过 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 到镇 2.
- 买一个苹果 50 日元在镇 2.
- 从城镇搬出 2 到镇 3.
- 卖一个苹果 200 日元在镇 3.
例如,如果 Aoki 改变了镇上苹果的价格 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