← 返回题目列表

AtCoder · abc250_g

G. 斯托克斯

中文机器翻译题面 查看原题

分数: 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