問題文

あなたは $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$

出力

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

入力例 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