配点 : $600$ 点

問題文

あなたは $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$ 円であるものとします。

制約

• 入力は全て整数
• $1 \le N \le 2 \times 10^5$
• $1 \le P_i \le 10^9$

入力

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

$N$

$P_1$ $P_2$ $\dots$ $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