Cho dãy gồm ~N~ số nguyên ~a_1, a_2, \dots, a_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 ~a_i, a_{i+1}, a_{i+2}, \dots, a_{j-1}, a_j~ ~(1 \le i \le j \le 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 nghiêm ngặt và dài nhất, nếu ~2~ dãy có độ dài bằng nhau thì đưa ra tổng lớn hơn.

Input

• Dòng đầu gồm một số nguyên dương ~N~ ~(N \le 10^6)~;

• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \dots, a_N~ ~(|a_i| \le 10^6, 1 \le i \le N)~.

Output

Một số duy nhất là kết quả tìm được của bài toán.

Scoring

Sample Input 1

6
1 2 3 1 5 7

Sample Output 1

13

Sample Input 2

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

Sample Output 2

1

Notes

• Ví dụ thứ nhất: Dãy: ~1, 5, 7~.

• Ví dụ thứ hai: Dãy: ~-5, 1, 2, 3~.