Cho dãy số nguyên A gồm \(n\) số nguyên \((a_{1},\ a_{2},\ \ldots,\ a_{n})\). Một dãy con liên tiếp của A là một dãy gồm các phần tử liên tiếp nhau trong A.

Yêu cầu: Hãy tìm dãy con liên tiếp có tổng các phần tử lớn nhất.

Dữ liệu vào:

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

- Dòng thứ hai ghi \(n\) số nguyên \(a_{1},\ a_{2},\ldots,\ a_{n}\ (\left| a_{i} \right| \leq 10^{6},\ 1 \leq i \leq n)\), mỗi số cách nhau một khoảng trắng.

Dữ liệu ra:

- Dòng đầu ghi tổng lớn nhất tìm được.

- Dòng thứ 2 ghi ra các phần tử của dãy con liên tiếp tìm được (giữ nguyên theo thứ tự ban đầu trong A). Mỗi phần tử cách nhau một khoảng trắng. Nếu có nhiều dãy như thế thì ghi ra dãy xuất hiện đầu tiên.

Ví dụ:

Ràng buộc:

• 40% test với \(0 < n \leq 10^{2}\).

• 40% test với \(10^{2} < n \leq 10^{4}\).

• 20% test với \(10^{4} < n \leq 10^{6}.\)