Đoạn con 3

Cho một dãy gồm $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Yêu cầu: Hãy chọn ra đúng $3$ đoạn con liên tiếp không giao nhau (không có phần tử chung) của dãy sao cho tổng các phần tử trong $3$ đoạn con đó là lớn nhất.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương $n$ ($3\le n\le {10}^5$).
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ ($|a_i|\le {10}^9$).

Dữ liệu ra

• Ghi ra một số nguyên duy nhất là tổng lớn nhất có thể đạt được.

Ví dụ