Trong giờ ôn tập môn Toán, cô giáo viết lên bảng một dãy gồm \(N\) số nguyên \(a_1, a_2, \dots, a_N\). Cô yêu cầu cả lớp: "Mỗi bạn được chọn một số số bất kỳ trên bảng, nhưng không được chọn hai số ở vị trí liền kề nhau". An là học sinh giỏi nhất lớp, cậu nhận thấy rằng nếu tất cả các số đều âm thì cách an toàn nhất là không chọn số nào, lúc đó tổng được coi là \(0\).

Cô giáo thách đố cả lớp: hãy tìm cách chọn sao cho tổng các số được chọn là lớn nhất. Hãy giúp An hoàn thành bài tập và chứng minh cho cả lớp thấy lời giải của mình.

Đị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\) (\(-10^9 \le a_i \le 10^9\)).

Định dạng đầu ra

• In ra tổng lớn nhất có thể đạt được.

Ví dụ

Input:

6
3 2 5 4 1 6

Output:

14

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.