AtCoder Regular Contest 063 ~

AtCoder Regular Contest 063

D - 高橋君と見えざる手 / An Invisible Hand

Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 400 点

問題文

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 円以上の利益を上げられることは仮定して構いません。

制約

  • 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. 町 1 から町 2 へ移動する。
  2. 町 2 で 50 円を支払い、リンゴを 1 個買う。
  3. 町 2 から町 3 へ移動する。
  4. 町 3 で 200 円でリンゴを 1 個売る。

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

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

入力例 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

Score : 400 points

Problem Statement

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

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

  • Move: When at town i (i < N), move to town i + 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 A_i yen (the currency of Japan) at town i (1 ≦ i ≦ N), where A_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 T. (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 A_i into another arbitrary non-negative integer A_i' for any town i, any number of times. The cost of performing this operation is |A_i - A_i'|. After performing this operation, different towns may have equal values of A_i.

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

Constraints

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

Input

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

N T
A_1 A_2 ... A_N

Output

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

Sample Input 1

3 2
100 50 200

Sample Output 1

1

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

  1. Move from town 1 to town 2.
  2. Buy one apple for 50 yen at town 2.
  3. Move from town 2 to town 3.
  4. Sell one apple for 200 yen at town 3.

If, for example, Aoki changes the price of an apple at town 2 from 50 yen to 51 yen, Takahashi will not be able to achieve the profit of 150 yen. The cost of performing this operation is 1, thus the answer is 1.

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

Sample Input 2

5 8
50 30 40 10 20

Sample Output 2

2

Sample Input 3

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

Sample Output 3

2

Submit提出する