D - An Invisible Hand Editorial /

Time Limit: 2 sec / Memory Limit: 256 MiB

配点 : 400400

問題文

NN 個の町が一直線上に並んでいます。行商人の高橋君は町 11 から出発し、リンゴの売買をしながら町 NN へと向かいます。

はじめ高橋君は町 11 におり、リンゴを 11 つも持っていません。高橋君は次のいずれかの行動を繰り返し行います。

  • 移動: 町 ii (i<Ni < N) にいるとき、町 i+1i + 1 へ移動する。
  • リンゴの売買: リンゴを好きな個数だけ売買する。ここで、町 ii (1iN1 ≦ i ≦ N) ではリンゴの買値も売値もともに AiA_i 円とする。ここで AiA_i は相異なる整数です。

11 つの町で売買するリンゴの個数に制限はありませんが、旅の中で売買するリンゴの個数は合計で (買う個数と売る個数を合わせて) TT 個以下にしなくてはなりません。

高橋君は旅の利益、すなわちリンゴを売った代金から買った代金を引いた値を最大にするように旅をするとします。旅が終わったときに持っていたリンゴの価値は考えず、旅の中で売買した金額だけを考えます。

この旅に先立って、青木君は任意の町 ii に対して AiA_i を好きな非負整数 AiA_i' に変えるという操作を好きなだけ行うことができます。ただし、この操作は行うごとに AiAi|A_i - A_i'| のコストがかかります。操作後には異なる町の間でリンゴの値段が同じになっていても構いません。

青木君の目的はできるだけ少ない合計コストの操作で高橋君の利益を少なくとも 11 円下げることです。合計コストの最小値を求めてください。

ただし、元の状態で高橋君が 11 円以上の利益を上げられることは仮定して構いません。

制約

  • 1N1051 ≦ N ≦ 10^5
  • 1Ai1091 ≦ A_i ≦ 10^9 (1iN1 ≦ i ≦ N)
  • AiA_i は相異なる
  • 2T1092 ≦ T ≦ 10^9
  • 入力の状態では高橋君は 11 円以上の利益を上げられることが保証される

入力

入力は以下の形式で標準入力から与えられる。

NN TT
A1A_1 A2A_2 ...... ANA_N

出力

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


入力例 1Copy

Copy
3 2
100 50 200

出力例 1Copy

Copy
1

この入力の状態では、高橋君は次のようにして最大の利益である 150150 円を達成することができます。

  1. 11 から町 22 へ移動する。
  2. 225050 円を支払い、リンゴを 11 個買う。
  3. 22 から町 33 へ移動する。
  4. 33200200 円でリンゴを 11 個売る。

たとえば、青木君が町 22 のリンゴの値段を 5050 円から 5151 円に変えると、高橋君はどのようにしても 150150 円の利益を上げることができなくなります。すなわち、コスト 11 で高橋君の利益を少なくとも 11 円下げることが可能であり、答えは 11 となります。

他にも、町 33 のリンゴの値段を 200200 円から 199199 円に変えることでもコスト 11 で高橋君の利益を下げることが可能です。


入力例 2Copy

Copy
5 8
50 30 40 10 20

出力例 2Copy

Copy
2

入力例 3Copy

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

出力例 3Copy

Copy
2

Score : 400400 points

Problem Statement

There are NN towns located in a line, conveniently numbered 11 through NN. Takahashi the merchant is going on a travel from town 11 to town NN, buying and selling apples.

Takahashi will begin the travel at town 11, with no apple in his possession. The actions that can be performed during the travel are as follows:

  • Move: When at town ii (i<Ni < N), move to town i+1i + 1.
  • Merchandise: Buy or sell an arbitrary number of apples at the current town. Here, it is assumed that one apple can always be bought and sold for AiA_i yen (the currency of Japan) at town ii (1iN1 ≦ i ≦ N), where AiA_i are distinct integers. Also, you can assume that he has an infinite supply of money.

For some reason, there is a constraint on merchandising apple during the travel: the sum of the number of apples bought and the number of apples sold during the whole travel, must be at most TT. (Note that a single apple can be counted in both.)

During the travel, Takahashi will perform actions so that the profit of the travel is maximized. Here, the profit of the travel is the amount of money that is gained by selling apples, minus the amount of money that is spent on buying apples. Note that we are not interested in apples in his possession at the end of the travel.

Aoki, a business rival of Takahashi, wants to trouble Takahashi by manipulating the market price of apples. Prior to the beginning of Takahashi's travel, Aoki can change AiA_i into another arbitrary non-negative integer AiA_i' for any town ii, any number of times. The cost of performing this operation is AiAi|A_i - A_i'|. After performing this operation, different towns may have equal values of AiA_i.

Aoki's objective is to decrease Takahashi's expected profit by at least 11 yen. Find the minimum total cost to achieve it. You may assume that Takahashi's expected profit is initially at least 11 yen.

Constraints

  • 1N1051 ≦ N ≦ 10^5
  • 1Ai1091 ≦ A_i ≦ 10^9 (1iN1 ≦ i ≦ N)
  • AiA_i are distinct.
  • 2T1092 ≦ T ≦ 10^9
  • In the initial state, Takahashi's expected profit is at least 11 yen.

Input

The input is given from Standard Input in the following format:

NN TT
A1A_1 A2A_2 ...... ANA_N

Output

Print the minimum total cost to decrease Takahashi's expected profit by at least 11 yen.


Sample Input 1Copy

Copy
3 2
100 50 200

Sample Output 1Copy

Copy
1

In the initial state, Takahashi can achieve the maximum profit of 150150 yen as follows:

  1. Move from town 11 to town 22.
  2. Buy one apple for 5050 yen at town 22.
  3. Move from town 22 to town 33.
  4. Sell one apple for 200200 yen at town 33.

If, for example, Aoki changes the price of an apple at town 22 from 5050 yen to 5151 yen, Takahashi will not be able to achieve the profit of 150150 yen. The cost of performing this operation is 11, thus the answer is 11.

There are other ways to decrease Takahashi's expected profit, such as changing the price of an apple at town 33 from 200200 yen to 199199 yen.


Sample Input 2Copy

Copy
5 8
50 30 40 10 20

Sample Output 2Copy

Copy
2

Sample Input 3Copy

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

Sample Output 3Copy

Copy
2


2025-07-26 (Sat)
22:56:58 +00:00