Mộc Châu là một điểm du lịch nổi tiếng của tỉnh Sơn La với nhiều thắng cảnh đẹp. Đặc biệt, dọc trên trục đường quốc lộ ~6~ người ta trồng rất nhiều cây đào và mận đan xen nhau. Đến mùa đông, hoa đào đỏ và hoa mận trắng nở xen kẽ nhau rất đẹp. Trên tuyến đường này người ta đếm được có ~N~ cây đào và mận được đánh số từ ~1~ đến ~N~, cây thứ ~i~ người ta đánh giá được có độ đẹp là số nguyên ~A_i~ (~1 \le i \le N~). Rất nhiều du khách đến đây vào mùa hoa đã muốn dùng Flycam để chụp những bức ảnh đẹp. Một bức ảnh đẹp là một bức ảnh chụp được một đoạn liên tiếp các cây đào và mận thỏa mãn:

• Có tối thiểu ~4~ cây.
• Số cây đào và mận bằng nhau.

Độ đẹp của bức ảnh được tính bằng tổng độ đẹp của các cây có trong bức ảnh đó.

Yêu cầu: Hãy tính độ đẹp lớn nhất của bức ảnh có thể chụp được.

Input

• Dòng đầu chứa số nguyên dương ~N~ (~4 \le N \le 3 \times 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, ..., A_N~ (~|A_i| \le 10^9~ với ~1 \le i \le N~). Hai số liên tiếp được ghi cách nhau một dấu cách.

Output

• Đưa ra một số nguyên duy nhất là độ đẹp lớn nhất của một bức ảnh có thể chụp được.

Sample Input 1

6
-4 3 -2 -6 7 2

Sample Output 1

2

Giải thích ví dụ

Chụp ~4~ cây số ~2, 3, 4, 5~ sẽ có độ đẹp là ~3 + (-2) + (-6) + 7 = 2~.

Subtasks