Dãy đẹp

Cho một dãy số \((a_n)\) gồm \(n\) số nguyên \(a_1,a_2,\dots,a_n\).
Một dãy số được gọi là dãy đẹp nếu mọi phần tử của nó đều không chia hết cho \(3\).

Dãy con của một dãy số là một phần tử hoặc một nhóm các phần tử liên tiếp trong dãy số đó.

Yêu cầu:
Trong tất cả các dãy con là dãy đẹp của dãy số \((a_n)\),
hãy tính tổng các phần tử của từng dãy con.
Trong các tổng thu được, hãy đưa ra giá trị lớn nhất.
Nếu không tồn tại dãy con là dãy đẹp thì in ra \(0\).

Input

• Dòng thứ nhất chứa số nguyên dương \(n\) \((1 \le n \le 2 \cdot 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)\), các số cách nhau bởi một dấu cách.

Output

Ghi ra một số nguyên duy nhất là kết quả của bài toán.

Scoring

• Subtask 1 (20%): \(n \le 10^3\).
• Subtask 2 (30%): Mọi \(a_i\) đều không chia hết cho \(3\).
• Subtask 3 (50%): Không có ràng buộc gì thêm.

Giải thích test ví dụ
Dãy số có các dãy con là dãy đẹp:
\(\{1\}, \{2\}, \{7\}, \{8\}, \{1,2\}, \{7,8\}\).
Trong đó, dãy con \(\{7,8\}\) có tổng các phần tử lớn nhất là \(15\).

Sample Input 1

5
1 2 3 7 8

Sample Output 1

15