Problem Description

There are candies arranged from $1$ to $n$ on a table, each with a deliciousness value $a_{i}$. You cannot eat two adjacent candies at the same time. You need to find the maximum sum of deliciousness values when eating $1, 2, 3, \ldots, \left \lceil \frac{n}{2} \right \rceil$ candies.

Input Format

The first line is a positive integer $n$.

The next $n$ lines each contain a number representing the deliciousness value $a_{i}$ of the $i$-th candy.

Output Format

There are $\left \lceil \frac{n}{2} \right \rceil$ lines, each representing the maximum sum of deliciousness values when eating $1, 2, 3, \ldots, \left \lceil \frac{n}{2} \right \rceil$ candies.

Sample Input and Output

Sample Input #1

5
3
5
1
7
6

Sample Output #1

7
12
10

Sample Input #2

20
623239331
125587558
908010226
866053126
389255266
859393857
596640443
60521559
11284043
930138174
936349374
810093502
521142682
918991183
743833745
739411636
276010057
577098544
551216812
816623724

Sample Output #2

936349374
1855340557
2763350783
3622744640
4439368364
5243250666
5982662302
6605901633
7183000177
7309502029

Notes/Hints

All data satisfies the following constraints:

$1 \le n \le 2 \times 10^{5}$

$1 \le a_{i} \le 10^{9}$

$8\%$ of the data satisfies: $1 \le n \le 2000$

There are no special constraints for the remaining test cases.

[Sample Explanation #1]

When eating only one candy, choosing the fourth one with a deliciousness value of $7$ is the maximum.

When eating two candies, choosing the second and fourth ones is optimal, with a deliciousness value of $5 + 7 = 12$.

When eating three candies, since you cannot eat two adjacent candies, you can only choose the first, third, and fifth ones, with a deliciousness value of $3 + 1 + 6 = 10$.

见题面 Input 部分

见题面 Output 部分