問題文

東西に細長い土地があります。 この土地は、N 個の区画が東西に並んだ形をしており、西から i 番目の区画は区画 i と呼ばれます。

それぞれの区画には地下資源があることがわかっており、区画 i の資源埋蔵量は A_i です。

1 以上 N 以下のそれぞれの整数 k について、次の問題の答えを求めてください。

• 連続する k 個の区画を選んだとき、それらの区画の資源埋蔵量の総和として考えられる最大値はいくらか。

制約

• 1 \leq N \leq 3000
• 1 \leq A_i \leq 10^9
• 入力される値はすべて整数である。

入力例 1

4
4 1 3 3

出力例 1

4
6
8
11

k=1 のとき、区画 1 を選ぶと資源埋蔵量の総和は 4 となり、これが最大です。

k=2 のとき、区画 3,4 を選ぶと資源埋蔵量の総和は 3+3=6 となり、これが最大です。

k=3 のとき、区画 1,2,3 を選ぶと資源埋蔵量の総和は 4+1+3=8 となり、これが最大です。

k=4 のとき、区画 1,2,3,4 を選ぶと資源埋蔵量の総和は 4+1+3+3=11 となり、これが最大です。

入力例 2

5
10 20 30 40 50

出力例 2

50
90
120
140
150

入力例 3

10
61049214 115057849 356385814 932678664 505961980 877482753 476308661 571830644 210047210 873430114

出力例 3

932678664
1438640644
2316123397
2792432058
3364262702
3720648516
4447740026
4804125840
4919183689
4980232903