Vì vừa đạt giải cao trong một kì thi nên bạn Quý được ban tổ chức trao thưởng. Thể lệ trao thưởng như sau:

• Có ~ n ~ bàn được xếp thành một hàng ngang, trên mỗi bàn chứa một món quà.
• Bạn Quý được chọn bất kì món quà nào, hoặc không chọn, nhưng không được chọn quá 2 món quà liên tiếp

Bạn hãy giúp Quý tính xem có thể chọn lượng quà có giá trị lớn nhất là bao nhiêu?

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương ~ n ~
• Dòng thứ hai ghi ~ n ~ số nguyên ~ a_1,a_2,…,a_n ~ thể hiện giá trị của ~ n ~ món quà.

Kết quả

In ra tổng giá trị các món quà lớn nhất mà bạn Quý có thể chọn.

Ràng buộc

• 40% số test có ~1 ≤ n ≤ 20 ~
• 60% số test còn lại có ~ 1 ≤ n ≤ 10^5 ~
• ~ 0 ≤ |a_i | ≤ 10^6 ~

Ví dụ:

Input 1

5
6 9 1 3 5 

Output 1

23