Cho một dãy số \((a_{n})\) gồm \(n\) số nguyên \(a_{1},a_{2},\ldots,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 kề trong dãy số đó.

Yêu cầu: Trong mỗi dãy con là dãy đẹp của dãy số \(\left( a_{n} \right)\), tính tổng tất cả các phần tử của dãy con này. Trong các tổng tính được, hãy đưa ra tổng có giá trị lớn nhất.

Dữ liệu vào:

- Dòng thứ nhất chứa số nguyên dương \(n\ (1 \leq n \leq {2.10}^{5})\).

- Dòng thứ hai chứa \(n\) số nguyên \(a_{1},a_{2},\ldots,a_{n}( - 10^{9} \leq a_{i} \leq 10^{9})\), các số cách nhau bởi dấu cách.

Kết quả ra:

• Một dòng chứa giá trị của tổng thỏa mãn yêu cầu. Trong trường hợp không tồn tại dãy con là dãy đẹp thì đưa ra số 0.

Ví dụ: