分数: 600 点
问题陈述
您将在下一个交易日交易 X 公司的股票 N 天。
作为预知者,您知道 i-第交易日将是 P_i 每单位日元(日本货币)。
每天,您都可以选择执行以下操作之一。
- 购买一单位股票 P_i 日元。
- 您将获得一单位股票,您的资金将减少 P_i 日元。
- 出售一单位库存 P_i 日元。
- 您将损失一单位股票,您的资金将增加 P_i 日元。
- 什么也不做。
你最初有 10^{100} 日元,让你永远不会缺钱。
找出当 N第一天已经结束。
即使您仍持有 X 公司的部分股票,当 N- 第一天结束了,认为他们值得 0 日元。
约束
- 输入中的所有值都是整数。
- 1 \le N \le 2 \times 10^5
- 1 \le P_i \le 10^9
输入
输入由标准输入按以下格式给出:
N P_1 P_2 \dots P_N
输出
将答案打印为整数。
示例输入 1
8 2 5 4 3 7 1 8 6
示例输出 1
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 日元到目前为止。
示例输入 2
5 10000 1000 100 10 1
示例输出 2
0
示例输入 3
15 300 1 4000 1 50000 900000000 20 600000 50000 300 50000 80000000 900000000 7000000 900000000
示例输出 3
2787595378