AT_pakencamp_2018_day3_d なぎさちゃんの別荘

[problemUrl]: https://atcoder.jp/contests/pakencamp-2018-day3/tasks/pakencamp_2018_day3_d なぎさちゃんの別荘は $ N $ 個の部屋と $ N-1 $ 本の通路からなり、各部屋には $ 1 $ から $ N $ の、各通路には $ 1 $ から $ N-1 $ の番号が割り振られています。$ i $ 番目の通路は部屋 $ i $ と 部屋 $ i+1 $ を双方向に繋いでおり、整数 $ C_i $ が書かれています。 いろはちゃんは今朝、この内のある部屋で目が覚めました。忍者であるいろはちゃんは、忍術を使って抜け出すことにしました。いろはちゃんの気分は整数で表され、これが高いほど忍術が成功しやすいです。気分の値は初め $ 0 $ であり、通路 $ i $ を通ると気分に $ C_i $ が加算されますが、仕掛けが作動してその通路が通れなくなります。 スタートする部屋を $ r $ として、通路を $ 0 $ 回以上通って好きな部屋で立ち止まるときの、気分の最大値を $ X_r $ とします。 全ての部屋 $ i $ に対して $ X_i $ を求めて下さい。

入力は、以下の形式で標準入力より与えられます。 > $ N $ $ C_1 $ $ C_2 $ $ C_3 $ ... $ C_{N-1} $

全部で $ N $ 行出力してください。 $ i $ 行目には $ X_i $ 、つまり部屋 $ i $ から始めたときの気分の最大値を出力してください。

### 制約 - $ 2\ \leq\ N\ \leq\ 100000 $ - $ -10^9\ \leq\ C_i\ \leq\ 10^9 $ ### 小課題 小課題 $ 1 $ \[$ 15 $ 点\] - $ N\ \leq\ 1000 $ を満たす。 - 全ての $ C_i $ は $ 0 $ 以上である。 小課題 $ 2 $ \[$ 30 $ 点\] - 全ての $ C_i $ は $ 0 $ 以上である。 小課題 $ 3 $ \[$ 55 $ 点\] - 追加の制約はない。 ### Sample Explanation 1 この入力例において、別荘の図は以下のようになっています。 !\[ \](https://img.atcoder.jp/pakencamp-2018-day3/5d34b4fad483077eede3689d4a4573f8.png) 例えば部屋 $ 3 $ から出発した場合、$ 3 $ → $ 2 $ → $ 1 $ というルートを通り部屋 $ 1 $ で立ち止まるとき、気分が $ 10\ +\ 70\ =\ 80 $ が得られます。 また、これより良い気分を得る方法はありません。 ### Sample Explanation 2 この入力は、小課題 $ 1,\ 2 $ の制約を満たしません。