Có ~n~ bảng số được đánh số từ ~1~ đến ~n~, bảng thứ ~i~ có điểm ~a_i~. Ở lượt chơi thứ ~i~, cần chọn đúng ~i~ bảng sao cho không có hai bảng nào kề nhau và tổng điểm lớn nhất.

Sau mỗi lượt, các bảng được trả lại vị trí cũ để phục vụ lượt tiếp theo.

Input

• Dòng đầu chứa số nguyên ~n~ ~(1 \le n \le 200000)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ ~(1 \le a_i \le 10^9)~.

Output

Gồm ~k~ dòng với ~k=n/2~ nếu ~n~ chẵn, ~k=(n+1)/2~ nếu ~n~ lẻ. Dòng thứ ~i~ in tổng điểm lớn nhất khi chọn đúng ~i~ bảng.

Subtask

• Subtask ~1~ có ~16\%~ số điểm: ~n \le 20~.
• Subtask ~2~ có ~16\%~ số điểm: ~n \le 2000~ và các ~a_i~ bằng nhau.
• Subtask ~3~ có ~18\%~ số điểm: ~n \le 2000~.
• Subtask ~4~ có ~50\%~ số điểm: không có ràng buộc gì thêm.

Ví dụ

5
1 6 4 9 8

9
15
13