Stonks

题目描述

你将在接下来的 $N$ 天内交易 X 公司的股票。 作为一个先知，你知道第 $i$ 天的股票价格将是每股 $P_i$ 日元（日本的货币）。 每天，你可以选择恰好执行以下操作之一。

以 $P_i$ 日元买入一股股票。 你将获得一股股票，你的金钱将减少 $P_i$ 日元。

以 $P_i$ 日元卖出一股股票。 你将失去一股股票，你的金钱将增加 $P_i$ 日元。

什么也不做。

你最初有 $10^{100}$ 日元，所以你永远不会缺钱。 求在第 $N$ 天结束时你最多可能拥有的净增金额。
即使在第 $N$ 天结束时你仍然持有一些 X 公司的股票，也视为它们价值 $0$ 日元。

输入格式

输入由标准输入提供，格式如下： $N$ $P_1$ $P_2$ $\dots$ $P_N$

输出格式

以整数形式输出答案。

8
2 5 4 3 7 1 8 6

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

提示

输入中的所有数值均为整数。 $1 \le N \le 2 \times 10^5$ $1 \le P_i \le 10^9$按如下操作，你的金钱将增加 $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$ 日元。

标签: AtCoder|abc250G

来源

AtCoder|abc250G