[ABC047D] 高橋君と見えざる手

# 高桥君和不可见之手 ## 问题描述 有 $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$ 円的利益。 ## 输入 输入按以下标准： $$ N \space T $$ $$ A_1 \space A_2 \space \dots \space A_N $$ ## 输出 输出使高桥君最大收益至少下降 $1$ 円的最小代价和。 ## 样例1解释 在初始状态下，高桥君能够进行以下的行动来获得最大收益( $150$ 円)： 1. 从小镇 $1$ 移动到小镇 $2$ 。 1. 在小镇 $2$ 处花 $50$ 円买一个苹果。 1. 从小镇 $2$ 移动到小镇 $3$ 。 1. 在小镇 $3$ 处卖掉一个苹果获得 $200$ 円。 举例来说，如果青木君把小镇 $2$ 的苹果单价从 $50$ 円上调至 $51$ 円，高桥君就无法获得 $150$ 円的收益。也就是说，此操作能够使高桥君的最大收益至少下降 $1$ 円，所以答案为 $1$ 。 另外，将小镇 $3$ 的苹果单价从 $200$ 円降至 $199$ 円也能够达到目的。

[problemUrl]: https://atcoder.jp/contests/abc047/tasks/arc063_b $ N $ 個の町が一直線上に並んでいます。行商人の高橋君は町 $ 1 $ から出発し、リンゴの売買をしながら町 $ N $ へと向かいます。 はじめ高橋君は町 $ 1 $ におり、リンゴを $ 1 $ つも持っていません。高橋君は次のいずれかの行動を繰り返し行います。 - 移動: 町 $ i $ ($ i\ <\ N $) にいるとき、町 $ i\ +\ 1 $ へ移動する。 - リンゴの売買: リンゴを好きな個数だけ売買する。ここで、町 $ i $ ($ 1\ ≦\ i\ ≦\ N $) ではリンゴの買値も売値もともに $ A_i $ 円とする。ここで $ A_i $ は相異なる整数です。 $ 1 $ つの町で売買するリンゴの個数に制限はありませんが、旅の中で売買するリンゴの個数は合計で (買う個数と売る個数を合わせて) $ T $ 個以下にしなくてはなりません。 高橋君は旅の利益、すなわちリンゴを売った代金から買った代金を引いた値を最大にするように旅をするとします。旅が終わったときに持っていたリンゴの価値は考えず、旅の中で売買した金額だけを考えます。 この旅に先立って、青木君は任意の町 $ i $ に対して $ A_i $ を好きな非負整数 $ A_i' $ に変えるという操作を好きなだけ行うことができます。ただし、この操作は行うごとに $ |A_i\ -\ A_i'| $ のコストがかかります。操作後には異なる町の間でリンゴの値段が同じになっていても構いません。 青木君の目的はできるだけ少ない合計コストの操作で高橋君の利益を少なくとも $ 1 $ 円下げることです。合計コストの最小値を求めてください。 ただし、元の状態で高橋君が $ 1 $ 円以上の利益を上げられることは仮定して構いません。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ T $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $

高橋君の収益を少なくとも $ 1 $ 円下げるために必要な合計コストの最小値を出力せよ。

3 2
100 50 200

1

5 8
50 30 40 10 20

2

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

2

### 制約 - $ 1\ ≦\ N\ ≦\ 10^5 $ - $ 1\ ≦\ A_i\ ≦\ 10^9 $ ($ 1\ ≦\ i\ ≦\ N $) - $ A_i $ は相異なる - $ 2\ ≦\ T\ ≦\ 10^9 $ - 入力の状態では高橋君は $ 1 $ 円以上の利益を上げられることが保証される ### Sample Explanation 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 $ で高橋君の利益を下げることが可能です。