题目描述

您打算在未来的 $N$ 天里交易 X 公司的股票。

作为一名先知，您知道第 $i$ 天的股票价格将是 $P_i$ 日元（日本的货币）每单位。

每天，您可以选择执行以下操作之一。

• 用 $P_i$ 日元购买一单位股票。
  • 您将获得一单位股票，您的资金将减少 $P_i$ 日元。
• 以 $P_i$ 日元的价格卖出一单位股票。
  • 您将失去一单位股票，您的资金将增加 $P_i$ 日元。
• 什么也不做。

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

找到第 $N$ 天结束时，您可能获得的最大金额。即使在第 $N$ 天结束时，您仍然持有一些 X 公司的股票，也视为这些股票价值为 $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$ 单位股票。现在您没有股票，您的资金到目前为止增加了 $3$ 日元。
• 在第 $3$ 天，您购买 $1$ 单位股票。现在您有 $1$ 单位股票，您的资金到目前为止增加了 $-1$ 日元。
• 在第 $4$ 天，您购买 $1$ 单位股票。现在您有 $2$ 单位股票，您的资金到目前为止增加了 $-4$ 日元。
• 在第 $5$ 天，您卖出 $1$ 单位股票。现在您有 $1$ 单位股票，您的资金到目前为止增加了 $3$ 日元。
• 在第 $6$ 天，您购买 $1$ 单位股票。现在您有 $2$ 单位股票，您的资金到目前为止增加了 $2$ 日元。
• 在第 $7$ 天，您卖出 $1$ 单位股票。现在您有 $1$ 单位股票，您的资金到目前为止增加了 $10$ 日元。
• 在第 $8$ 天，您卖出 $1$ 单位股票。现在您没有股票，您的资金到目前为止增加了 $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