Tìm chuỗi con có trọng số lớn nhất của một dãy số cho trước
- Cho một dãy số s = <a₁, ..., a_n>
- Một chuỗi con sẽ là s(i,j) = <a_i, ..., a_j>, 1≤i≤j≤n
- Trọng số được tính theo công thức:

- Vấn đề: tìm chuỗi con có trọng số lớn nhất

Input

Dòng đầu tiên là số nguyên dương n, n 0≤n≤200

Dòng thứ 2 là n số nguyên, các số cách nhau bằng một khoảng cách

Output

Trọng số lớn nhất cần tìm

Example

Input:
6
-2 11 -4 13 -5 2

Output
20