Contest Duration: - (local time) (100 minutes) Back to Home
G - Stonks /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

あなたは N 日にわたって、 X 社の株の取引を行います。

あなたは、毎日以下の行動をどれか 1 つだけ行うことが出来ます。

• X 社の株を 1 株、 P_i 円で買う。
• このとき、持ち株が 1 株増え、所持金が P_i 円減少する。
• X 社の株を 1 株、 P_i 円で売る。この行動は株を 1 株以上保有している時行える。
• このとき、持ち株が 1 株減り、所持金が P_i 円増加する。
• 何もしない。

あなたの取引開始時の所持金は 10^{100} 円なので、現金に困ることはありません。

N 日目の行動を終えた時点で、所持金の増加額としてありうる最大値を求めてください。
なお、 N 日目の行動を終えた時点でまだ X 社の株をいくつか保有していても、それは所持金の計算上 0 円であるものとします。

### 制約

• 入力は全て整数
• 1 \le N \le 2 \times 10^5
• 1 \le P_i \le 10^9

### 入力

N
P_1 P_2 \dots P_N


### 入力例 1

8
2 5 4 3 7 1 8 6


### 出力例 1

16


• 1 日目、株を 1 株買う。 持ち株は 1 株、所持金の増加額は -2 円になる。
• 2 日目、株を 1 株売る。 持ち株は 0 株、所持金の増加額は 3 円になる。
• 3 日目、株を 1 株買う。 持ち株は 1 株、所持金の増加額は -1 円になる。
• 4 日目、株を 1 株買う。 持ち株は 2 株、所持金の増加額は -4 円になる。
• 5 日目、株を 1 株売る。 持ち株は 1 株、所持金の増加額は 3 円になる。
• 6 日目、株を 1 株買う。 持ち株は 2 株、所持金の増加額は 2 円になる。
• 7 日目、株を 1 株売る。 持ち株は 1 株、所持金の増加額は 10 円になる。
• 8 日目、株を 1 株売る。 持ち株は 0 株、所持金の増加額は 16 円になる。

### 入力例 2

5
10000 1000 100 10 1


### 出力例 2

0


### 入力例 3

15
300 1 4000 1 50000 900000000 20 600000 50000 300 50000 80000000 900000000 7000000 900000000


### 出力例 3

2787595378


Score : 600 points

### Problem Statement

You are going to trade stocks of Company X for the next N days.

As a precognitive, you know that the stock price on the i-th day of trading will be P_i yen (the currency in Japan) per unit.

Every day, you can choose to do exactly one of the following.

• Buy one unit of stock for P_i yen.
• You will obtain one unit of stock and your money will decrease by P_i yen.
• Sell one unit of stock for P_i yen.
• You will lose one unit of stock and your money will increase by P_i yen.
• Do nothing.

You initially have 10^{100} yen, so you will never be short of money.

Find the maximum possible amount of money you will have gained when the N-th day has ended.
Even if you still possess some amount of stocks of Company X when the N-th day has ended, it is considered that they are worth 0 yen.

### Constraints

• All values in input are integers.
• 1 \le N \le 2 \times 10^5
• 1 \le P_i \le 10^9

### Input

Input is given from Standard Input in the following format:

N
P_1 P_2 \dots P_N


### Output

Print the answer as an integer.

### Sample Input 1

8
2 5 4 3 7 1 8 6


### Sample Output 1

16


By acting as follows, your money will increase by 16 yen, which is the maximum possible.

• On the 1-th day, you buy 1 unit of stock. You now have 1 unit of stock, and your money has increased by -2 yen so far.
• On the 2-nd day, you sell 1 unit of stock. You now have 0 units of stocks, and your money has increased by 3 yen so far.
• On the 3-rd day, you buy 1 unit of stock. You now have 1 unit of stock, and your money has increased by -1 yen so far.
• On the 4-th day, you buy 1 unit of stock. You now have 2 units of stocks, and your money has increased by -4 yen so far.
• On the 5-th day, you sell 1 unit of stock. You now have 1 unit of stock, and your money has increased by 3 yen so far.
• On the 6-th day, you buy 1 unit of stock. You now have 2 units of stocks, and your money has increased by 2 yen so far.
• On the 7-th day, you sell 1 unit of stock. You now have 1 unit of stock, and your money has increased by 10 yen so far.
• On the 8-th day, you sell 1 unit of stock. You now have 0 units of stocks, and your money has increased by 16 yen so far.

### Sample Input 2

5
10000 1000 100 10 1


### Sample Output 2

0


### Sample Input 3

15
300 1 4000 1 50000 900000000 20 600000 50000 300 50000 80000000 900000000 7000000 900000000


### Sample Output 3

2787595378