Cho dãy gồm N số nguyên a,, a2,..., n. Dãy con gồm các phần tử liên tiếp kề nhau thuộc dãy đã cho có dạng ai, ai+1, ai+2 ... aj-1, aj; (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 đầu vào: 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^6).

• Dòng thứ hai chứa N số nguyên a1, a2, ..., an (0 ≤ |ai| ≤ 10^6 ,1 ≤ i≤ N).

Kết quả: Ghi vào tệp văn bàn SEQ11.OVT

Dữ liệu đầu ra: 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.

Input 01:

6
1 2 3 1 5 7

Output 01:

13

Giải thích: Dãy: 1 5 7

Input 02:

8
-1 -2 3 4 -5 1 2 3

Output 02:

1

Giải thích: Dãy: -5 1 2 3

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ủa bài có: n ≤ 10^6.