高桥君和不可见之手

问题描述

有 $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$ 円的利益。

数据范围

• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$
• $A_i$ 相异
• $2 \leq T \leq 10^9$
• 保证初始状态下高桥君至少能获得 $1$ 円的利益。

输入

输入按以下标准：

输出

输出使高桥君最大收益至少下降 $1$ 円的最小代价和。

样例1解释

在初始状态下，高桥君能够进行以下的行动来获得最大收益( $150$ 円)：

1. 从小镇 $1$ 移动到小镇 $2$ 。
2. 在小镇 $2$ 处花 $50$ 円买一个苹果。
3. 从小镇 $2$ 移动到小镇 $3$ 。
4. 在小镇 $3$ 处卖掉一个苹果获得 $200$ 円。

举例来说，如果青木君把小镇 $2$ 的苹果单价从 $50$ 円上调至 $51$ 円，高桥君就无法获得 $150$ 円的收益。也就是说，此操作能够使高桥君的最大收益至少下降 $1$ 円，所以答案为 $1$ 。

另外，将小镇 $3$ 的苹果单价从 $200$ 円降至 $199$ 円也能够达到目的。