Dãy con không giảm

Cho một dãy số gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^6, 1 \leq i \leq n \leq 10^6\)).

**Yêu cầu:** Tìm dãy con có tổng các phần tử là lớn nhất trong các dãy con không giảm, nếu có nhiều dãy con thoả mãn thì in ra các dãy con theo thứ tự xuất hiện.

Input

Vào từ file SUBSEQ.INP gồm:

• Dòng đầu: số nguyên dương \(n\);
• Dòng tiếp theo: \(n\) số nguyên dương cách nhau khoảng trắng.

Output

Ghi ra file SUBSEQ.OUT gồm:

• Dòng đầu: tổng lớn nhất tìm được;
• Các dòng tiếp theo: các dãy con thỏa mãn.

Example

10
2 2 3 4 6 6 7 7 8 8

53
2 2 3 4 6 6 7 7 8 8 

11
4 7 4 5 7 4 9 3 3 4 6

16
4 5 7 
3 3 4 6 

Scoring

Ràng buộc:

• Có 20% số điểm ứng với \(n = 10\) và 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 ứng với \((10^3 < n \leq 10^6)\).