Có \(n\) gói quà được xếp thành một hàng, gói quà thứ i có giá trị là a_i (1 ≤ i ≤ N). Nam được chọn số lượng quà tùy ý nhưng không được chọn quá 2 gói quà cạnh nhau.

Yêu cầu: Em hãy giúp Nam lựa chọn để đạt được tổng giá trị quà lớn nhất.

Dữ liệu vào:

+ Dòng đầu tiên chứa một số nguyên dương \(n\ (1 \leq n \leq 10^{5})\).

+ Dòng thứ hai chứa \(n\) số nguyên \(a_{1},\ a_{2},\ ...,\ a_{n}\) thể hiện giá trị của \(n\) gói quà \((0 < a_{i} \leq \ 10^{6},\ 1 \leq i \leq n)\).

Kết quả:

+ Ghi một số nguyên là tổng giá trị các gói quà lớn nhất mà bạn Nam có thể chọn.

Ví dụ:

Ràng buộc:

+ 40% số test với \(1\ \leq n \leq \ 20\)

+ 60% số test với \(1\ \leq \ n\ \leq \ 10^{5}\)