Bài 18: Hịch xuất quân

Yêu cầu: Đang trong quá trình chuẩn bị cho cuộc khởi nghĩa năm 40 SCN từ Mê Linh đến Luy Lâu, có ~N~ ngôi làng nằm dọc theo tuyến đường hành quân. Ngôi làng thứ ~i~ sẵn sàng đóng góp ~A_i~ nghĩa quân. Tuy nhiên, để tránh bứt dây động rừng làm quân thù sinh nghi, lệnh truyền xuống là: Tuyệt đối không được thu nạp quân ở 2 ngôi làng nằm liền kề nhau. Hãy tính toán chiến lược hành quân để thu được tổng số nghĩa quân lớn nhất.

Giới hạn:

• ~1 \le N \le 10^5~
• ~1 \le A_i \le 10^9~
• Thời gian: 1.0s | Bộ nhớ: 256 MB

Ví dụ:

Input:

5
5 1 2 10 4

Output:

15

(Giải thích: Chọn làng 1 (5 quân), bỏ làng 2, bỏ làng 3, chọn làng 4 (10 quân). Tổng là 15.)