Hai bạn Bờm và Cuội lại rủ nhau chơi trò chơi thứ hai như sau: Các bạn có ~n~ bảng số nguyên được đánh số từ ~1~ đến ~n~, mỗi bảng mang một số nguyên dương là số điểm mà các bạn nhận được khi chọn bảng đó. Trò chơi được chia thành ~k~ lượt chơi (~k = \frac{n}{2}~ nếu ~n~ chẵn, ~k = \frac{n+1}{2}~ nếu ~n~ lẻ).

Tại lượt chơi thứ ~i~, các bạn cần chọn ra ~i~ bảng số sao cho tổng điểm là lớn nhất và không được chọn đồng thời hai bảng số nào có số thứ tự liên tiếp nhau. Sau khi hoàn thành mỗi lượt chơi các bạn phải trả lại các bảng số đã chọn về vị trí cũ để phục vụ lượt chơi tiếp theo.

Yêu cầu

Hãy lập trình chương trình giải quyết bài toán trên.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất gồm một số nguyên dương ~n~ ~(1 \le n \le 200000)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_i~ ~(1 \le a_i \le 10^9)~ là số điểm của mỗi bảng số.

Dữ liệu đầu ra

Gồm ~k~ dòng, dòng thứ ~i~ ghi ra điểm tối đa mà bạn Bờm và Cuội có thể đạt được tại lượt ~i~.

Ràng buộc dữ liệu

• Subtask 1 (16% điểm): ~n \le 20~.
• Subtask 2 (16% điểm): ~n \le 2000; a_1 = a_2 = \ldots = a_{n - 1} = a_n~.
• Subtask 3 (18% điểm): ~n \le 2000~.
• Subtask 4 (50% điểm): Không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

5
1 6 4 9 8

OUTPUT

9
15
13

Giải thích:

• Lượt ~1~ chọn vị trí: ~4~.
• Lượt ~2~ chọn vị trí: ~2~ và ~4~.
• Lượt ~3~ chọn vị trí: ~1~, ~3~ và ~5~.