Trong lộ trình xây dựng Đà Nẵng trở thành "Thành phố thông minh", thành phố triển khai một hệ thống camera AI để quản lý và tối ưu hóa dòng chảy giao thông tại các tuyến đường huyết mạch như Trần Phú, Bạch Đằng, Lê Duẩn...

Hệ thống ghi nhận lưu lượng xe tại \(n\) điểm kiểm soát liên tiếp, tạo thành một dãy số nguyên dương \(a_1, a_2, \dots, a_n\). Vào những giờ cao điểm, việc tính toán lưu lượng và phân phối cho các phương tiện giao thông là một trong những nhiệm vụ hết sức cần thiết đối với trung tâm điều hành.

Yêu cầu: Cho \(n\) điểm kiểm soát \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9, 1 \le i \le n\)), điểm thứ \(i\) có lưu lượng \(a_i\) xe. Hãy tính tổng lưu lượng xe lớn nhất của \(n\) điểm kiểm soát trên nhưng phải thoả điều kiện không lấy \(3\) điểm liên tiếp.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 10^6\)) là số điểm kiểm soát.
• Dòng thứ \(2\) chứa \(n\) số nguyên \(a_i\) là lưu lượng xe tại điểm kiểm soát thứ \(i\) (\(1 \le a_i \le 10^9\)).

Output

• Ghi ra một số nguyên là giá trị lớn nhất tìm được.

Example

4
9 3 5 4

18

6
6 10 13 9 8 1

33

Scoring

• Có \(30\%\) số tests ứng với \(30\%\) số điểm thoả mãn: \(1 \le n \le 100; 1 \le a_i \le 10^5\).
• Có \(30\%\) số tests ứng với \(30\%\) số điểm thoả mãn: \(100 < n \le 10^5; 1 \le a_i \le 10^4\).
• Có \(40\%\) số tests ứng với \(40\%\) số điểm thoả mãn: \(10^5 < n \le 10^6; 10^4 < a_i \le 10^9\).