あなたのトレジャーハンターチームは、貴金属や貴重な骨董品でいっぱいの巨大な遺跡を発見しました。この遺跡は、一直線上に並んだ $n$ 個の掘削地点で構成されています。

初期計画では、各掘削地点にはそれぞれ純利益が設定されています。$i$ 番目の地点の利益は $p_i$ です。具体的には、これは $i$ 番目の地点を 1 メートル掘るごとにチームが $p_i$ ドルの利益を得ることを意味します。$p_i$ は負の値になることもあり、その場合はその地点を掘削する機械の運転コストが、掘削による実際の利益を上回っていることを意味します。

当然のことながら、最も利益の出る地点をできるだけ深く掘りたいところです。しかし、地滑りを防ぐため、急すぎる斜面を作ることは許可されていません。より正確には、隣接する任意の 2 つの地点において、掘削深さの差が 1 メートルを超えてはなりません。特に、1 番目と $n$ 番目の地点は、最大でも 1 メートルまでしか掘ることができません。

これらの条件下で得られる最大の純利益はいくらでしょうか？

例えば、最初の入力例において最適となる有効な掘削計画を以下に示します。この計画による純利益は 8 です。

入力

入力の 1 行目には、正の整数 $n$ ($1 \le n \le 250\,000$) が含まれます。 入力の 2 行目には、$n$ 個の整数 $p_i$ ($-10^6 \le p_i \le 10^6$) が空白区切りで含まれます。

出力

得られる最大の利益を整数で 1 つ出力してください。

入出力例

入力 1

5
1 3 -4 2 1

出力 1

8

入力 2

4
1 1 -2 3

出力 2

5

入力 3

5
-1 -3 0 -5 -4

出力 3

0