Bác Ba làm bảo vệ cho một khu phố có \(N\) ngôi nhà xếp thành hàng ngang. Mỗi đêm trước khi đi tuần, bác ghi lại giá trị tài sản ước tính của từng ngôi nhà vào sổ tay: nhà thứ \(i\) có giá trị \(a_i\) đồng. Bác phải lên kế hoạch đi tuần sao cho không bao giờ ghé hai ngôi nhà cạnh nhau trong cùng một ca, vì dân trong khu sẽ rất nghi ngờ.

Bác Ba muốn chọn ra một số ngôi nhà để ghé, sao cho tổng giá trị tài sản ghi nhận được là lớn nhất. Hãy giúp bác tính tổng giá trị lớn nhất bác có thể đạt được trong một ca tuần.

Định dạng đầu vào

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 2 \times 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).

Định dạng đầu ra

• In ra tổng giá trị tài sản lớn nhất bác Ba có thể thu được.

Ví dụ

Input:

5
3 2 5 4 1

Output:

8

Ràng buộc

• \(20\%\) số điểm ứng với \(N \le 20\).
• \(30\%\) số điểm ứng với \(N \le 2000\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.