Cho dãu gồm \(n\) số nguyên \(a_{1},a_{2},\ldots,a_{n}\). Tìm dãy con gồm một hoặc một số phần tử liên tiếp của dãy đã cho với tổng các phần tử trong dãy là lớn nhất.

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên dương \(n\ (n \leq 10^{6})\).

+ Dòng thứ \(i\) trong \(n\) dòng tiếp theo ghi số nguyên \(a_{i}\ (\left| a_{i} \right| \leq 10^{8})\).

Kết quả:

+ Dòng đầu ghi vị trí của phần tử đầu tiên của dãy tìm được.

+ Dòng thứ hai ghi vị trí cuối cùng của dãy con tìm được.

+ Dòng thứ ba ghi tổng các phần tử của dãy con tìm được.

Dữ liệu luôn đảm bảo kết quả là duy nhất.

Ví dụ:

Input	Output
8 12 -14 1 23 -6 22 -34 13	3 6 40