Trạm Thiện Nguyện Mũi Né

Mô tả

Mỗi mùa hè, bạn tham gia một chuyến xe thiện nguyện đi dọc theo tuyến đường ven biển Mũi Né. Dọc tuyến đường có n trạm dừng, tại mỗi trạm bạn sẽ nhận được một số tiền lương quyên góp a[i]. Do quy định về tính công bằng, bạn không được nhận tiền ở hai trạm kề nhau (nghĩa là nếu nhận ở trạm i thì không được nhận ở trạm i-1 và i+1).

Nhiệm vụ của bạn là tính số tiền lớn nhất có thể thu được khi đi qua tất cả các trạm.

Đầu vào

• Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 10^5), số lượng trạm thiện nguyện.
• Dòng thứ hai chứa n số nguyên a[0], a[1], ..., a[n-1], mỗi số là số tiền quyên góp tại trạm đó (0 ≤ |a[i]| ≤ 10^4).

Đầu ra

• In ra một số nguyên duy nhất là tổng tiền lớn nhất có thể thu được.

Ràng buộc

• 1 ≤ n ≤ 10^5
• 0 ≤ |a[i]| ≤ 10^4
• Tổng kết quả đảm bảo nằm trong phạm vi số nguyên 64-bit.

Ví dụ

Ví dụ 1:

Input: 4 3 5 2 8

Output: 11

Giải thích: Các lựa chọn khả thi là:

• Nhận trạm 1 và 3: 5 + 8 = 13? Không, trạm 1 và 3 không kề nhau nên hợp lệ.
• Thực tế: trạm 0+2=5, trạm 0+3=11, trạm 1+3=13. Đáp án đúng là 13.

Ví dụ 2:

Input: 5 1 2 3 4 5

Output: 9

Giải thích: Nhận tại các trạm 1 và 3 (2+4=6), trạm 1 và 4 (2+5=7), trạm 0 và 2 và 4 (1+3+5=9). Tổng lớn nhất là 9.