/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
あなたは N 日にわたって、 X 社の株の取引を行います。
未来予知の能力者であるあなたは、取引のうち i 日目の X 社の株価が 1 株あたり P_i 円であることを知っています。
あなたは、毎日以下の行動をどれか 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
以下のように行動することで所持金を 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