Candies

Time limit5sMemory limit512 MB

Summary

For each j, find the maximum sum of j non-adjacent values chosen from N candies in a row.

Level: Hard9 of 10
Topics: Dynamic programming, Greedy, Heap, Implementation
Solved: No attempts yet

Problem

There are N candies in a row on the table. Each candy has a value called deliciousness. The deliciousness of the candy which is located i-th from the left is $A_i$ ( $1 \le i \le N$ ).

JOI-chan decided to eat some of these N candies. JOI-chan wants to maximize the sum of deliciousness of candies which she is going to eat.

However, JOI-chan thinks that just choosing candies greedily is not interesting, so she makes a rule that she cannot choose two consecutive candies simultaneously.

JOI-chan has not decided how many candies she eats, so JOI-chan wants to know, for each $j$ ( $1 \le j \le \lceil N/2 \rceil$ ), the maximum sum of deliciousness of candies when she eats j candies. Here $\lceil x \rceil$ is the smallest integer larger than or equal to x.

Given the number of candies and the deliciousness of candies, write a program which calculates, for each $j$ ( $1 \le j \le \lceil N/2 \rceil$ ), the maximum sum of deliciousness of candies when she eats j candies.

Input

Read the following data from the standard input.

The first line of input contains an integer N. This means there are N candies on the table.
The i-th line ( $1 \le i \le N$ ) of the following N lines contains an integer $A_i$ . This means the deliciousness of the candy which is located i-th from the left is $A_i$ .

Output

Write $\lceil N/2 \rceil$ lines to the standard output. The j-th line ( $1 \le j \le \lceil N/2 \rceil$ ) of output contains the maximum sum of deliciousness of candies when she eats j candies.

Constraints

$1 \le N \le 200\,000$ .
$1 \le A_i \le 1\,000\,000\,000$ ( $1 \le i \le N$ ).

Examples2

Example 1
Input
```
5
3
5
1
7
6
```
Expected output
```
7
12
10
```

Example 2

Input

Expected output