Có \(N\) viên kẹo được xếp thành một hàng trên bàn. Mỗi viên kẹo có một giá trị gọi là độ ngon. Độ ngon của viên kẹo thứ \(i\) từ trái sang là \(A_i\).

JOI-chan quyết định ăn một số viên kẹo và muốn tổng độ ngon của những viên mình ăn là lớn nhất. Tuy nhiên, cô cảm thấy việc chỉ chọn những viên ngon nhất không thú vị, nên đặt ra quy tắc: không được chọn đồng thời hai viên kẹo nằm cạnh nhau.

JOI-chan chưa quyết định sẽ ăn bao nhiêu viên. Với mỗi số nguyên \(j\) thỏa mãn \(1 \le j \le \lceil N/2 \rceil\), hãy tính tổng độ ngon lớn nhất có thể đạt được khi cô ăn đúng \(j\) viên kẹo. Ký hiệu \(\lceil x\rceil\) là số nguyên nhỏ nhất lớn hơn hoặc bằng \(x\).

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\), là số viên kẹo trên bàn.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(A_i\), là độ ngon của viên kẹo thứ \(i\) từ trái sang.

Dữ liệu ra

In \(\lceil N/2\rceil\) dòng. Dòng thứ \(j\) chứa tổng độ ngon lớn nhất khi JOI-chan ăn đúng \(j\) viên kẹo mà không chọn hai viên kề nhau.

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(1 \le A_i \le 1\,000\,000\,000\) với \(1 \le i \le N\).

Phân nhóm

1. \(8\) điểm: \(N \le 2000\).
2. \(92\) điểm: Không có ràng buộc bổ sung.

Ví dụ

5
3
5
1
7
6

7
12
10

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

936349374
1855340557
2763350783
3622744640
4439368364
5243250666
5982662302
6605901633
7183000177
7309502029

Nguồn

JOI 2018, trại huấn luyện mùa xuân, ngày thi 4: Candies.