Problem Description

There is a long, narrow land stretching east to west. This land is divided into $ N $ sections arranged east to west, and the $ i $-th section from the west is called section $ i $.

Each section is known to have underground resources, and the amount of resources in section $ i $ is $ A_i $.

For each integer $ k $ between $ 1 $ and $ N $ (inclusive), find the answer to the following question:

• When choosing $ k $ consecutive sections, what is the maximum possible sum of the resource deposits in these sections?

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ $\cdots$ $ A_N $

Output Format

Output $ N $ lines. The $ k $-th line should contain the maximum sum of the resource deposits in $ k $ consecutive sections.

Sample Input and Output

Sample Input #1

4
4 1 3 3

Sample Output #1

4
6
8
11

Sample Input #2

5
10 20 30 40 50

Sample Output #2

50
90
120
140
150

Sample Input #3

10
61049214 115057849 356385814 932678664 505961980 877482753 476308661 571830644 210047210 873430114

Sample Output #3

932678664
1438640644
2316123397
2792432058
3364262702
3720648516
4447740026
4804125840
4919183689
4980232903

Notes/Hints

Constraints

• $1 \leq N \leq 3000$
• $1 \leq A_i \leq 10^9$
• All values input are integers.

Sample Explanation 1

For $ k=1 $, choosing section $ 1 $ gives a sum of resource deposits of $ 4 $, which is the maximum. For $ k=2 $, choosing sections $ 3,4 $ gives a sum of resource deposits of $ 3+3=6 $, which is the maximum. For $ k=3 $, choosing sections $ 1,2,3 $ gives a sum of resource deposits of $ 4+1+3=8 $, which is the maximum. For $ k=4 $, choosing sections $ 1,2,3,4 $ gives a sum of resource deposits of $ 4+1+3+3=11 $, which is the maximum.

见题面 Input 部分

见题面 Output 部分