Cho dãy số nguyên \(a_1, a_2, \ldots, a_n\), một dãy con liên tiếp của dãy \(a\) là \(a_l, a_{l + 1}, \ldots, a_{r}\) có trọng số là tổng \(a_l + a_{l + 1} + \ldots + a_{r}\). Hãy tìm dãy con liên tiếp có trọng số lớn nhất, hay tìm một cặp \((l, r)\) mà \(1\le l\le r\le n\) có \((a_l + a_{l + 1} + \ldots + a_{r})\) là lớn nhất.

Input

• Dòng đầu chứa số nguyên dương \(n\) \((n \le 10^5)\).
• Dòng thứ hai chứa \(n\) số \(a_1, a_2, ..., a_n\) \((|a_i|\le 10^4)\).

Output

• Ghi ra tổng lớn nhất tìm được.

Example

10
3 -1 -3 5 2 5 0 -1 5 4

20