G - Stonks

得分 : $600$ 分

问题描述

你打算在接下来的 $N$ 天中交易公司 X 的股票。

作为一个预知能力者，你知道第 $i$ 天交易时股票的价格为 $P_i$ 日元（日本的货币单位）每单位。

每天，你可以选择只做以下的一个动作。

• 以 $P_i$ 日元的价格购买一单位的股票。
  • 你将得到一单位的股票，你的资金将减少 $P_i$ 日元。
• 以 $P_i$ 日元的价格卖出一单位的股票。
  • 你将失去一单位的股票，你的资金将增加 $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$

输出

以整数形式输出答案。

8
2 5 4 3 7 1 8 6

16

通过以下操作，你的资金将增加 $16$ 日元，这是最大可能的。

• 在第 $1$ 天，购买 $1$ 单位的股票。 你现在有 $1$ 单位的股票，你的资金迄今已增加 $-2$ 日元。
• 在第 $2$ 天，卖出 $1$ 单位的股票。 你现在没有股票，你的资金迄今已增加 $3$ 日元。
• 在第 $3$ 天，购买 $1$ 单位的股票。 你现在有 $1$ 单位的股票，你的资金迄今已增加 $-1$ 日元。
• 在第 $4$ 天，购买 $1$ 单位的股票。 你现在有 $2$ 单位的股票，你的资金迄今已增加 $-4$ 日元。
• 在第 $5$ 天，卖出 $1$ 单位的股票。 你现在有 $1$ 单位的股票，你的资金迄今已增加 $3$ 日元。
• 在第 $6$ 天，购买 $1$ 单位的股票。 你现在有 $2$ 单位的股票，你的资金迄今已增加 $2$ 日元。
• 在第 $7$ 天，卖出 $1$ 单位的股票。 你现在有 $1$ 单位的股票，你的资金迄今已增加 $10$ 日元。
• 在第 $8$ 天，卖出 $1$ 单位的股票。 你现在没有股票，你的资金迄今已增加 $16$ 日元。

5
10000 1000 100 10 1

0

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

2787595378