AT_abc250_g [ABC250G] Stonks

题目描述

你将在 $N$ 天内进行 X 公司的股票交易。

作为拥有预知未来能力的人，你已经知道第 $i$ 天 X 公司的股价为每股 $P_i$ 日元。

你每天只能进行以下三种操作中的一种：

• 以 $P_i$ 日元买入 X 公司的 1 股股票。
  • 此时，你的持股数增加 1，所持现金减少 $P_i$ 日元。
• 以 $P_i$ 日元卖出 X 公司的 1 股股票。只有当你持有至少 1 股时才能进行此操作。
  • 此时，你的持股数减少 1，所持现金增加 $P_i$ 日元。
• 什么都不做。

你在交易开始时拥有 $10^{100}$ 日元的现金，因此无需担心现金不足。

请你求出，在第 $N$ 天的操作结束后，你的现金增加额的最大可能值。 注意，在第 $N$ 天操作结束后，如果你还持有 X 公司的股票，这些股票在现金计算中按 $0$ 日元计价。

输入格式

输入以如下格式从标准输入给出。

$N$ $P_1$ $P_2$ $\dots$ $P_N$

输出格式

请输出最大现金增加额，结果为整数。

输入输出样例 #1

输入 #1

8
2 5 4 3 7 1 8 6

输出 #1

16

输入输出样例 #2

输入 #2

5
10000 1000 100 10 1

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

2787595378

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq P_i \leq 10^9$

样例说明 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$ 日元。

由 ChatGPT 4.1 翻译