题目描述

あなたは $N$ 日にわたって、 X 社の株の取引を行います。

未来予知の能力者であるあなたは、取引のうち $i$ 日目の X 社の株価が $1$ 株あたり $P_i$ 円であることを知っています。

あなたは、毎日以下の行動をどれか $1$ つだけ行うことが出来ます。

• X 社の株を $1$ 株、 $P_i$ 円で買う。
  • このとき、持ち株が $1$ 株増え、所持金が $P_i$ 円減少する。
• X 社の株を $1$ 株、 $P_i$ 円で売る。この行動は株を $1$ 株以上保有している時行える。
  • このとき、持ち株が $1$ 株減り、所持金が $P_i$ 円増加する。
• 何もしない。

あなたの取引開始時の所持金は $10^{100}$ 円なので、現金に困ることはありません。

$N$ 日目の行動を終えた時点で、所持金の増加額としてありうる最大値を求めてください。
なお、 $N$ 日目の行動を終えた時点でまだ X 社の株をいくつか保有していても、それは所持金の計算上 $0$ 円であるものとします。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $P_1$ $P_2$ $\dots$ $P_N$

输出格式

答えを整数として出力せよ。

题目大意

你要买一家公司的股票，现在你知道每天这个股票值 $p_i$ 元。

每天你要么买进一股，要么卖出一股，或者不操作，不能进行多个操作。

如果第 $n$ 天结束后还有剩余的股票，作废。

问你最多能得多少钱？注意，你最开始很富有，不会担心买不起股票。

$n \le 2 \times 10^5$，$p_i \le 10^9$。

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$

Sample Explanation 1

以下のように行動することで所持金を $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$ 円になる。