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 (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 từ thiết bị vào chuẩn:

• 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 \le i \le N\); \(|A_i| \le 10^9\)) mô tả các phần tử của dãy số.

Kết quả ghi ra thiết bị ra chuẩn:

• 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.