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≤n≤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à ~ (1≤a_i≤10^6, 1≤i≤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ụ:

Input

5
7 3 9 5 4 

Output

21 

Ràng buộc:

• 40% số test với ~ 1 ≤n≤ 20 ~
• 60% số test với ~ 1 ≤ n ≤ 10^5 ~