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

• Có N bàn xếp thành một hàng ngang, trên mỗi bàn chứa một món quà.
• Kim Chi đượ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 Chi tính xem có thể chọn lượng quà có giá trị lớn nhất là bao nhiêu?

Dữ liệu

• Dòng đầu ghi một số nguyên N.
• Dòng thứ hai ghi N số nguyên A₁, A₂,..., 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à Kim Chi có thể chọn.

Ví dụ

Input	Output
5 6 9 1 3 5	23

Giới hạn
• 40% số test có 1 ≤ N ≤ 20
• 60% số test còn lại có 1 ≤ N ≤ 10⁵
• 0 ≤ |Ai| ≤ 10⁶