AtCoder Beginner Contest 250
翻译中…
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.
翻译中…
样例
Input #1
8
2 5 4 3 7 1 8 6
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.
Input #2
5
10000 1000 100 10 1
Output #2
0
Input #3
15
300 1 4000 1 50000 900000000 20 600000 50000 300 50000 80000000 900000000 7000000 900000000
Output #3
2787595378
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。