Cho dãy gồm N số nguyên ~a₁, a₂, ..., aₙ~. Dãy con gồm các phần tử liên tiếp kề nhau thuộc dãy đã cho có dạng ~aᵢ, aᵢ₊₁, aᵢ₊₂, ..., aⱼ₋₁, aⱼ~ (1 ≤ i ≤ j ≤ N), độ dài của dãy con gồm các phần tử liên tiếp kề nhau bằng số lượng phần tử của dãy.

Yêu cầu: Tính tổng các phần tử của dãy con liên tiếp tăng dần và dài nhất nếu 2 dãy có độ dài bằng nhau thì đưa ra dãy có tổng lớn hơn.

Dữ liệu:

Từ tệp văn bản SEQ11.INP có cấu trúc:

• Dòng thứ nhất gồm một số nguyên dương N (N ≤ 10⁶).

• Dòng thứ hai chứa N số nguyên a₁, a₂, ..., aₙ (0 ≤ |aᵢ| ≤ 10⁶, 1 ≤ i ≤ N).

Kết quả:

Ghi vào tệp văn bản SEQ11.OUT

• Một số duy nhất là tổng lớn nhất của các phần tử trong dãy con tìm được.

Ví dụ đầu vào:

6
1 2 3 1 5 7

Đầu ra:

13

Ràng buộc:

• Có 40% số điểm của bài có: N ≤ 100.

• Có 30% số điểm của bài có: N ≤ 5000.

• Có 30% số điểm còn lại: N ≤ 10⁶.