Vì luôn luôn bị Rotund làm phiền, đám bạn của cậu quyết tâm dựa vào khẩu quyết lấy thịt đè người, lấy độc trị độc để báo thù. Thay vì liên tục bị thách đố, họ sẽ chủ động hợp sức nghĩ ra các câu đố khó hơn cho Rotund làm.

Lần này, thấy Rotund vừa làm xong một bài toán liên quan đến dãy con liên tiếp, đám bạn liền muốn tận dụng chủ đề này nhưng phải khác đi một chút để tạo độ khó cho Rotund. Họ nghĩ ra một câu đố như sau:

• Cho một dãy số nguyên.
• Hãy tìm cách chọn ra một số phần tử của dãy ban đầu (không cần liên tiếp) để tạo ra một dãy số nguyên mới có tổng lớn nhất.

Nhưng nghĩ đi nghĩ lại, đề bài này vẫn quá đơn giản và chưa để làm khó được Rotund bao lâu, nên đám bạn quyết định thêm vào một điều kiện nữa:

• Các phần tử cần được chọn sao cho cứ mỗi 4 phần tử liên tiếp trong dãy ban đầu phải có chẵn số được chọn vào dãy mới.
• Nghĩa là, Rotund chỉ được chọn phần tử ~a_i~ ~(4≤i≤n)~ nếu cậu đã chọn lẻ số phần tử trong 3 phần tử ~a_{i-1}~, ~a_{i-2}~, ~a_{i-3}~.

Thấy các bạn chủ động đưa ra lời thách thức với mình, Rotund rất vui mừng vì giờ cậu không còn phải tự một mình nghĩ ra những bài tập nữa. Cậu nhanh chóng suy nghĩ và muốn làm sao để tìm ra được kết quả câu đố nhanh nhất có thể.

Yêu cầu

Đưa ra tổng lớn nhất của dãy số mới được tạo ra từ những phần tử của dãy ban đầu theo điều kiện đề bài.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(1≤n≤10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ ~(1≤|a_i|≤10^9, 1≤i≤n)~.

Output

Một dòng duy nhất chứa kết quả bài toán.

Sample Input 1

10
-5 7 1 -7 1 8 -5 -8 -1 -4

Sample Output 1

7

Giải thích

Chọn các số ở vị trí 2, 3, 6, 7, 10

Sample Input 2

10
-6 3 -5 4 -4 -8 -6 -7 -1 -2

Sample Output 2

0

Giải thích

Không chọn số nào cả, dãy mới rỗng

Subtask

• Có 50% số test ứng với 50% số điểm có ~n≤20~;
• 50% số test còn lại tương ứng với 50% số điểm không có giới hạn gì thêm.