Cho một dãy số nguyên A gồm N phần tử. Hãy tìm ba đoạn con liên tiếp (mỗi đoạn có ít nhất một phần tử) không giao nhau của dãy số sao cho tổng các phần tử của ba đoạn con này là lớn nhất.

Dữ liệu vào:

• Dòng đầu tiên gồm một số nguyên dương N ($3\le N\le {10}^5$) mô tả số phần tử của dãy số;
• Dòng thứ hai gồm N số nguyên $A_i$ (1 ≤ i ≤ N; $|A_i|\le {10}^9$) mô tả các phần tử của dãy số.

Kết quả:

• Gồm một số nguyên là kết quả của bài toán.

Ví dụ:

Ràng buộc:

• Có 40% số test ứng với 40% số điểm có: $N\le {10}^2$;
• 30% số test khác ứng với 30% số điểm có: $N\le {10}^3$;
• 30% số test còn lại ứng với 30% số điểm không có ràng buộc gì thêm.