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=n/2 nếu n chẵn, k=(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 (nhập từ bàn phím/thiết bị vào chuẩn)

Dòng 1: Một số nguyên dương n 1≤n≤200000;

Dòng 2: Gồm n số nguyên dương ~a_i~ (~1≤a_i≤10^9~) là số điểm của mỗi bảng số.

Kết quả (ghi ra màn hình/thiết bị ra chuẩn)

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.

Ví dụ:

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.

Subtasks

• Subtask 1 (16% điểm): n≤20;
• Subtask 2 (16% điểm): n ≤ 2000;a1=a2=...=an;
• Subtask 3 (18% điểm): n≤2000;

• Subtask 4 (50% điểm): Không có ràng buộc gì thêm.

  Tài liệu tham khảo