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

[problemUrl]: https://atcoder.jp/contests/abc047/tasks/arc063_b $ N $ 個の町が一直線上に並んでいます。行商人の高橋君は町 $ 1 $ から出発し、リンゴの売買をしながら町 $ N $ へと向かいます。 はじめ高橋君は町 $ 1 $ におり、リンゴを $ 1 $ つも持っていません。高橋君は次のいずれかの行動を繰り返し行います。 - 移動: 町 $ i $ ($ i\

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

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

### 制約 - $ 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 $ で高橋君の利益を下げることが可能です。