AT_abc250_g [ABC250G] Stonks

[problemUrl]: https://atcoder.jp/contests/abc250/tasks/abc250_g あなたは $ 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 $

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

### 制約 - 入力は全て整数 - $ 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 $ 円になる。