(subseqnb.*)

Cho một dãy số gồm n số nguyên dương \(a_{1},\ a_{2},\ \ldots\ ,\ a_{n}\ (1 \leq n \leq 10^{6};\ 1 \leq a_{i} \leq 10^{6})\). Xét các dãy con là dãy các phần tử liên tiếp nhau của dãy ban đầu, mà trong đó các phần tử là không giảm \((a_{i} \leq a_{i + 1} \leq \ldots \leq a_{j - 1} \leq a_{j};\ 1 \leq i \leq j \leq \ n)\).

Yêu cầu: Tìm các dãy con có tổng các phần tử là lớn nhất trong các dãy con trên.

Dữ liệu vào:

• Dòng đầu tiên ghi số nguyên dương \(n\);

• Dòng tiếp theo ghi \(n\) số nguyên dương, mỗi số cách nhau một khoảng trắng.

Kết quả:

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

• Mỗi dòng tiếp theo, mỗi dòng ghi ra các phần tử của một dãy con tìm được.

Ví dụ:

Ràng buộc:

• Có 20% số điểm ứng với: \(n\ = \ 10\) và dãy ban đầu là một dãy không giảm;

• Có 20% số điểm ứng với \((11\ \leq \ n\ \leq \ 200)\);

• Có 20% số điểm ứng với \((201\ \leq \ n\ \leq \ 10^{3})\);

• 40% số điểm còn lại không có ràng buộc gì thêm.