Bác John sở hữu một dải đất rộng lớn được chia làm ~n~ lô đất liền kề nhau, được đánh số từ ~1~ đến ~n~. Theo kết quả khảo sát thổ nhưỡng, lô đất thứ ~i~ nếu đem vào canh tác sẽ mang lại một mức lợi nhuận (hoặc thua lỗ) dự kiến là ~a_i~ (~1 \le i \le n~).

Bác John quyết định không tự canh tác mà sẽ cho hai công ty nông nghiệp khác nhau thuê lại hai đoạn đất riêng biệt. Mỗi đoạn đất là một dãy các lô đất liên tiếp nhau có lợi nhuận tương ứng là ~a_i, a_{i+1},\dots,a_j~ (~1 \le i \le j \le n~). Tuy nhiên, do yêu cầu về quy chuẩn của máy móc nông nghiệp cỡ lớn, cả hai công ty đều yêu cầu số lượng lô đất họ thuê trong mỗi đoạn phải là một số chia hết cho ~3~ (ví dụ: ~3, 6, 9,\dots~ lô). Đồng thời, để tránh tranh chấp, hai đoạn đất này không được phép có lô đất nào chung.

Yêu cầu: Hãy giúp hai công ty chọn ra hai đoạn đất thỏa mãn các điều kiện trên sao cho tổng lợi nhuận dự kiến thu được từ hai đoạn đất là lớn nhất. (Lưu ý: luôn có cách chọn ra đúng hai đoạn đất, ngay cả khi tổng lợi nhuận có thể bị âm).

Input

• Dòng đầu ghi số nguyên ~n~ (~6 \le n \le 2 \cdot 10^5~).

• Dòng thứ hai ghi ~n~ số nguyên ~a_1, a_2,\dots,a_n~ (~|a_i| \le 10^9, 1 \le i \le n~).

Các số trên một dòng cách nhau bởi một dấu cách.

Output

• Một số duy nhất là tổng lợi nhuận lớn nhất của hai đoạn đất tìm được.

Scoring

Sample Input 1

11
-1 3 -1 -9 -1 1 1 1 1 1 -9

Sample Output 1

5

Notes

Đoạn đất ~\{-1,3,-1\}~ có lợi nhuận là ~1~, số lượng lô đất là ~3~, đoạn đất ~\{-1,1,1,1,1,1\}~ có lợi nhuận là ~4~ và số lượng lô đất là ~6~. Hai đoạn đất có tổng lợi nhuận là ~5~.