股票交易

题目描述

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

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

每天，你恰好可以选择执行以下操作之一。

以 $P_i$ 日元买入一股股票。

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

以 $P_i$ 日元卖出一股股票。

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

什么都不做。

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

求第 $N$ 天结束时你能获得的最大金额。

即使第 $N$ 天结束时你仍然持有一些 X 公司的股票，它们也被视为价值 $0$ 日元。

输入格式

输入按以下格式从标准输入给出：

N
P_1 P_2 … P_N

输出格式

将答案作为整数输出。

样例

8
2 5 4 3 7 1 8 6

16

按如下方式行动，你的钱会增加 $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$ 日元。

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$