Cho dãy số nguyên A gồm n số nguyên (a₁, a₂, ..., 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:

File daycon.inp gồm 2 dòng:

Dòng đầu ghi số nguyên dương n (0 < n ≤ 10⁶).

Dòng thứ hai ghi n số nguyên a₁, a₂, ..., a_n (|a_i| ≤ 10⁶, 1 ≤ i ≤ n), mỗi số cách nhau một khoảng trắng.

Dữ liệu ra:

File daycon.out gồm 2 dòng:

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

Dòng thứ hai 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ụ:

daycon.inp

6
-2 3 -2 3 1 -2

daycon.out

5
3 -2 3 1

Giải thích:

Trong các dãy con liên tiếp thì dãy gồm các phần tử: 3 -2 3 1 có tổng bằng 5 là lớn nhất.

Ràng buộc:

40% test với 3 < n ≤ 10⁵

40% test với 10⁵ < n ≤ 10⁹

20% test với 10⁹ < n ≤ 10¹⁰