Thành viên quanghieu18112013 nổi tiếng trên nền tảng LQDOJ với biệt danh "Thánh Nổ". Để duy trì hình ảnh một cựu học sinh giỏi nhưng lại cực kỳ lười biếng, Hiếu lên kế hoạch chọn làm một số bài tập trong danh sách \(N\) bài tập được đánh số từ \(1\) đến \(N\). Bài tập thứ \(i\) mang lại cho Hiếu \(A_i\) điểm "sống ảo" (giá trị \(A_i\) có thể âm nếu bài đó làm sai và bị cộng đồng bóc phốt).

Để không bị mang tiếng là lười biếng quá mức nhưng cũng không muốn làm quá nhiều bài gây tổn hại sức khỏe, Hiếu đề ra các quy tắc chọn bài như sau:

• Không giải 2 bài liên tiếp trong danh sách (tức là khoảng cách giữa 2 bài được chọn liên tiếp ít nhất là \(2\)).
• Không bỏ qua quá \(2\) bài liên tiếp (tức là khoảng cách giữa \(2\) bài được chọn liên tiếp không quá \(3\)).
• Bài đầu tiên được chọn phải là bài \(1\) hoặc bài \(2\).
• Bài cuối cùng được chọn phải là bài \(N-1\) hoặc bài \(N\).

Hãy giúp quanghieu18112013 tính tổng điểm "sống ảo" lớn nhất có thể đạt được nếu chọn tập các bài tập thỏa mãn các quy tắc trên.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(2 \le N \le 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\)).

Output

• In ra một số nguyên duy nhất là tổng điểm "sống ảo" lớn nhất tìm được.

Example

5
3 -1 4 2 5

12

4
10 20 -5 30

50

Scoring

• Subtask 1 (30 điểm): \(2 \le N \le 20\).
• Subtask 2 (70 điểm): \(2 \le N \le 10^5\).