Hiếu là một người yêu thích các thuật toán và thường xuyên tìm cách giải quyết các bài toán tối ưu. Hôm nay, Hiếu được cô giáo giao cho một mảng số nguyên gồm N phần tử, nhiệm vụ của Hiếu là tìm tổng lớn nhất của một dãy con liên tiếp bất kỳ trong mảng a. Một dãy con được định nghĩa là một tập hợp các phần tử liên tiếp trong mảng. Hiếu đã không thể giải bài toán này sau 2 ngày, bạn hãy giúp Hiếu nhé.

Input

Dòng đầu tiên chứ 1 số nguyên N (1 ≤ N ≤ 10⁵).
Dòng tiếp theo chứ n số nguyên a_i (-100 ≤ a_i ≤ 100).

Output

In ra tổng lớn nhất của một dãy con liên tiếp

Sample Input

5
1 2 3 -4 -5

Sample Output

6