시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 7 7 7 100.000%

문제

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).

예제 입력 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