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.

Ví dụ:

Input

5
6 9 1 3 5

Output

23

Giới hạn:

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