Gấu Trắng phát hiện bản thân quên mất một điều: ngoài kỹ năng giải mã, cậu còn cần phải đánh bại quái vật bằng tiếng đàn, chứng minh tài năng âm nhạc trong thế giới này mới xứng đáng sở hữu Quả Cầu Âm Thanh. Với mong muốn level up sức mạnh âm nhạc, cậu đã cùng hàng nghìn thí sinh khác tham dự Kỳ Tranh Tài để dành lấy Bí Kíp Âm Nhạc – quyển cẩm nang sẽ giúp cậu tiến xa trên con đường của chính mình.

Kỳ Tranh Tài đã chính thức bắt đầu! Câu hỏi có nội dung như sau:

Cho một mảng ~a~ gồm ~N~ phần tử nguyên. Hãy chọn ra một số đoạn con không đụng nhau từ mảng ~a~ (đoạn con thứ ~i~ và đoạn con thứ ~i+1~ được ngăn cách bởi ít nhất một vị trí trong mảng ~a~) sao cho tổng của các phần tử đầu và cuối của tất cả các đoạn con được chọn chia hết cho ~3~, đồng thời tổng giá trị các phần tử trong các đoạn đó là lớn nhất.

Nói cách khác, hãy chọn ~k~ (~k~ bất kỳ) đoạn con thỏa các điều kiện sau:

• Một cách chọn hợp lệ là chọn ~k~ đoạn con ~[u_1, v_1], [u_2, v_2], ..., [u_k, v_k]~ thỏa đồng thời tất các điều kiện sau:

  • ~1 \le u_1 \le v_k \le N~.

  • ~u_i \leq v_i~ (~1 \leq i \leq k~).

  • ~v_i + 1 < u_{i+1}~ (~1 \leq i < k~).

  • ~\sum_{i=1}^k a_{u_i} + a_{v_i}~ ~\vdots~ ~3~.

• Gọi ~s_i~ là tổng của đoạn con thứ ~i~ (~s_i = \sum_{j=u_i}^{v_i} a_j~). Tìm cách chọn ~k~ đoạn sao cho tổng ~S~ lớn nhất (với ~S = \sum_{i=1}^{k} s_i~, tức ~S~ là tổng của tất cả ~k~ đoạn).

• Không chọn bất kì một đoạn con nào cũng là một cách chọn hợp lệ.

Input

• Dòng đầu chứa số ~N~ ~(1 \le N\le 10^6)~.

• Dòng tiếp theo chứa ~N~ phần tử biểu diễn mảng ~a~ (~|a_i| \le 10^9~).

Output

Một số duy nhất là tổng ~S~ lớn nhất có thể của bài toán.

Scoring

• Subtask ~1~ (~15\%~): ~n \leq 20~.

• Subtask ~2~ (~15\%~): Mọi phần tử trong mảng đều chia hết cho ~3~.

• Subtask ~3~ (~20\%~): ~n \leq 100~.

• Subtask ~4~ (~30\%~): ~n \leq 1000~.

• Subtask ~5~ (~20\%~): Không có giới hạn gì thêm.

Sample Input 1

9
-1 2 -3 -5 -3 1 -2 -2 4

Sample Output 1

6

Notes

• Cách chọn: 2 đoạn ~[2, 2], [9, 9]~.

• Tổng lớn nhất tìm được là ~6 = a_2 + a_9 = 2 + 4~.

• Điều kiện 2 được thỏa mãn: ~a_2 + a_2 + a_9 + a_9 = 2 + 2 + 4 + 4 = 12~ ~\vdots~ ~3~