

Time Limit: 2 sec / Memory Limit: 256 MiB
配点 : 点
問題文
個の町が一直線上に並んでいます。行商人の高橋君は町 から出発し、リンゴの売買をしながら町 へと向かいます。
はじめ高橋君は町 におり、リンゴを つも持っていません。高橋君は次のいずれかの行動を繰り返し行います。
- 移動: 町 () にいるとき、町 へ移動する。
- リンゴの売買: リンゴを好きな個数だけ売買する。ここで、町 () ではリンゴの買値も売値もともに 円とする。ここで は相異なる整数です。
つの町で売買するリンゴの個数に制限はありませんが、旅の中で売買するリンゴの個数は合計で (買う個数と売る個数を合わせて) 個以下にしなくてはなりません。
高橋君は旅の利益、すなわちリンゴを売った代金から買った代金を引いた値を最大にするように旅をするとします。旅が終わったときに持っていたリンゴの価値は考えず、旅の中で売買した金額だけを考えます。
この旅に先立って、青木君は任意の町 に対して を好きな非負整数 に変えるという操作を好きなだけ行うことができます。ただし、この操作は行うごとに のコストがかかります。操作後には異なる町の間でリンゴの値段が同じになっていても構いません。
青木君の目的はできるだけ少ない合計コストの操作で高橋君の利益を少なくとも 円下げることです。合計コストの最小値を求めてください。
ただし、元の状態で高橋君が 円以上の利益を上げられることは仮定して構いません。
制約
- ()
- は相異なる
- 入力の状態では高橋君は 円以上の利益を上げられることが保証される
入力
入力は以下の形式で標準入力から与えられる。
出力
高橋君の収益を少なくとも 円下げるために必要な合計コストの最小値を出力せよ。
入力例 1Copy
3 2 100 50 200
出力例 1Copy
1
この入力の状態では、高橋君は次のようにして最大の利益である 円を達成することができます。
- 町 から町 へ移動する。
- 町 で 円を支払い、リンゴを 個買う。
- 町 から町 へ移動する。
- 町 で 円でリンゴを 個売る。
たとえば、青木君が町 のリンゴの値段を 円から 円に変えると、高橋君はどのようにしても 円の利益を上げることができなくなります。すなわち、コスト で高橋君の利益を少なくとも 円下げることが可能であり、答えは となります。
他にも、町 のリンゴの値段を 円から 円に変えることでもコスト で高橋君の利益を下げることが可能です。
入力例 2Copy
5 8 50 30 40 10 20
出力例 2Copy
2
入力例 3Copy
10 100 7 10 4 5 9 3 6 8 2 1
出力例 3Copy
2
Score : points
Problem Statement
There are towns located in a line, conveniently numbered through . Takahashi the merchant is going on a travel from town to town , buying and selling apples.
Takahashi will begin the travel at town , with no apple in his possession. The actions that can be performed during the travel are as follows:
- Move: When at town (), move to town .
- 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 yen (the currency of Japan) at town (), where 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 . (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 into another arbitrary non-negative integer for any town , any number of times. The cost of performing this operation is . After performing this operation, different towns may have equal values of .
Aoki's objective is to decrease Takahashi's expected profit by at least yen. Find the minimum total cost to achieve it. You may assume that Takahashi's expected profit is initially at least yen.
Constraints
- ()
- are distinct.
- In the initial state, Takahashi's expected profit is at least yen.
Input
The input is given from Standard Input in the following format:
Output
Print the minimum total cost to decrease Takahashi's expected profit by at least yen.
Sample Input 1Copy
3 2 100 50 200
Sample Output 1Copy
1
In the initial state, Takahashi can achieve the maximum profit of yen as follows:
- Move from town to town .
- Buy one apple for yen at town .
- Move from town to town .
- Sell one apple for yen at town .
If, for example, Aoki changes the price of an apple at town from yen to yen, Takahashi will not be able to achieve the profit of yen. The cost of performing this operation is , thus the answer is .
There are other ways to decrease Takahashi's expected profit, such as changing the price of an apple at town from yen to yen.
Sample Input 2Copy
5 8 50 30 40 10 20
Sample Output 2Copy
2
Sample Input 3Copy
10 100 7 10 4 5 9 3 6 8 2 1
Sample Output 3Copy
2