Cho dãy số ~A~ gồm ~n~ số nguyên. Một đoạn con liên tục có độ dài chia hết cho ~3~ được xét theo tổng các phần tử của nó.

Yêu cầu: Tìm tổng lớn nhất của một đoạn con liên tục có độ dài chia hết cho ~3~.

Input

Đọc từ file văn bản DAYSO.INP.

• Dòng đầu chứa số nguyên ~n~ ~(3 \le n \le 1000)~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ với ~|a_i| < 10^6~.

Output

Ghi ra file văn bản DAYSO.OUT một số nguyên là tổng lớn nhất tìm được.

Example input 1

4
-1 5 -10 1

Example output 1

-4