TA là một người rất thích Toán và những dãy số, và đặc biệt anh ấy rất thích con số 3 :)). Mặc dù chưa đến Tết nhưng anh đã nói ngocbi09 chuẩn bị quà sẵn. Nhưng để được quà thì anh ấy phải giải cho admin 1 bài liên quan đến số 3 yêu thích của anh.

Cho dãy số gồm n số nguyên a₁, a₂, ..., a_n. Một đoạn con của dãy đã cho là dãy a_i,..., a_j (1 ≤ i ≤ j ≤ n).

Nhiệm vụ của TA bây giờ chính là tìm đoạn con có độ dài (j - i+1) chia hết cho 3 mà có trọng số lớn nhất. <3 (Đây là dấu trái tim, không liên quan đến đề bài)

Giải thích Trọng số 1 đoạn (i,j) là tổng a[i]+....+a[j].

P/s: From TEAM VOI 2020 with love <3

Dữ liệu nhập:

- Dòng đầu ghi số nguyên n (3 ≤ n ≤ 300.000).
- Dòng thứ hai ghi n số nguyên a₁, a₂, ..., a_n (|a_i| < 3*10⁹).

Dữ liệu xuất:

- Giá trị trọng số của đoạn con tìm dược.