Score : $600$ points

问题描述

你将在接下来的 $N$ 天内交易公司 X 的股票。

作为一名先知，你知道第 $i$ 天交易时的股价为每股 $P_i$ 日元（日本货币单位）。

每天，你可以选择执行以下操作之一：

• 花费 $P_i$ 日元购买一股股票。
  • 你将获得一股股票，并且你的资金将减少 $P_i$ 日元。
• 以 $P_i$ 日元的价格卖出一股股票。
  • 你将失去一股股票，并且你的资金将增加 $P_i$ 日元。
• 什么都不做。

最初你拥有 $10^{100}$ 日元，因此你永远不会缺钱。

计算当第 $N$ 天结束时，你能获得的最大金额。 即使在第 $N$ 天结束时你还持有公司 X 的一定数量的股票，这些股票也被认为价值为 $0$ 日元。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 10:41:56