시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB166755740.141%

## 문제

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 Ai (1 ≤ i ≤ 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 ≤ j ≤ ⌈N/2⌉), the maximum sum of deliciousness of candies when she eats j candies. Here ⌈x⌉ 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 ≤ j ≤ ⌈N/2⌉), the maximum sum of deliciousness of candies when she eats j candies.

## 입력

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 ≤ i ≤ N) of the following N lines contains an integer Ai. This means the deliciousness of the candy which is located i-th from the left is Ai.

## 출력

Write ⌈N/2⌉ lines to the standard output. The j-th line (1 ≤ j ≤ ⌈N/2⌉) of output contains the maximum sum of deliciousness of candies when she eats j candies.

## 제한

• 1 ≤ N ≤ 200 000.
• 1 ≤ Ai ≤ 1 000 000 000 (1 ≤ i ≤ N).

번호배점제한
18
• N ≤ 2 000.
292

## 예제 입력 1

5
3
5
1
7
6


## 예제 출력 1

7
12
10


## 예제 입력 2

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


## 예제 출력 2

936349374
1855340557
2763350783
3622744640
4439368364
5243250666
5982662302
6605901633
7183000177
7309502029


## 채점 및 기타 정보

• 예제는 채점하지 않는다.